寬度優先搜尋
BFS寬度優先搜尋算法（又稱廣度優先搜尋）是最簡便的圖的搜尋算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都採用了和寬度優先搜尋類似的思想。
已知圖G=(V,E)和一個源頂點s，寬度優先搜尋以一種系統的方式探尋G的邊，從而“發現”s所能到達的所有頂點，並計算s到所有這些頂點的距離(最少邊數)，該算法同時能生成一棵根為s且包括所有可達頂點的寬度優先樹。對從s可達的任意頂點v，寬度優先樹中從s到v的路徑對應於圖G中從s到v的最短路徑，即包含最小邊數的路徑。該算法對有向圖和無向圖同樣適用。
之所以稱之為寬度優先算法，是因為算法自始至終一直通過已找到和末找到頂點之間的邊界向外擴展，就是說，算法首先搜尋和s距離為k的所有頂點，然後再去搜尋和S距離為k+l的其他頂點。
為了保持搜尋的軌跡，寬度優先搜尋為每個頂點著色：白色、灰色或黑色。算法開始前所有頂點都是白色，隨著搜尋的進行，各頂點會逐漸變成灰色，然後成為黑色。在搜尋中第一次碰到一頂點時，我們說該頂點被發現，此時該頂點變為非白色頂點。因此，灰色和黑色頂點都已被發現，但是，寬度優先搜尋算法對它們加以區分以保證搜尋以寬度優先的方式執行。若(u,v)∈E且頂點u為黑色，那么頂點v要么是灰色，要么是黑色，就是說，所有和黑色頂點鄰接的頂點都已被發現。灰色頂點可以與一些白色頂點相鄰接，它們代表著已找到和未找到頂點之間的邊界。
在寬度優先搜尋過程中建立了一棵寬度優先樹，起始時只包含根節點，即源頂點s.在掃描已發現頂點u的鄰接表的過程中每發現一個白色頂點v，該頂點v及邊(u,v)就被添加到樹中。在寬度優先樹中，我們稱結點u 是結點v的先輩或父母結點。因為一個結點至多只能被發現一次，因此它最多只能有--個父母結點。相對根結點來說祖先和後裔關係的定義和通常一樣：如果u處於樹中從根s到結點v的路徑中，那么u稱為v的祖先，v是u的後裔。
下面的寬度優先搜尋過程BFS假定輸入圖G=(V,E)採用鄰接表表示，對於圖中的每個頂點還採用了幾種附加的數據結構，對每個頂點u∈V，其色彩存儲於變數color【u】中，結點u的父母存於變數π【u】中。如果u沒有父母(例如u=s或u還沒有被檢索到)，則 π【u】=NIL，由算法算出的源點s和頂點u之間的距離存於變數d【u】中，算法中使用了一個先進先出佇列Q來存放灰色節點集合。其中head【Q】表示佇列Q的隊頭元素，Enqueue(Q,v)表示將元素v入隊， Dequeue(Q)表示對頭元素出隊；Adj【u】表示圖中和u相鄰的節點集合。
procedure BFS(G,S);
begin1. for 每個節點u∈V【G】- do
begin
2. color【u】←White;
3. d【u】←∞;
4. π【u】←NIL;
end;
5. color【s】←Gray;
6. d【s】←0;
7. π【s】←NIL;
8. Q←
9. while Q≠φ do
begin
10. u←head【Q】;
11. for 每個節點v∈Adj【u】 do
12. if color【v】=White then
begin
13.color【v】←Gray;
14.d【v】←d【v】+1;
15.π【v】←u;
16.Enqueue(Q,v);
end;
17. Dequeue(Q);
18. color【u】←Black;
end;
end;
圖1展示了用BFS在例圖上的搜尋過程。黑色邊是由BFS產生的樹枝。每個節點u內的值為d【u】，圖中所示的佇列Q是第9-18行while循環中每次疊代起始時的佇列。佇列中每個結點下面是該結點與源結點的距離。
圖1 BFS在一個無向圖上的執行過程
過程BFS按如下方式執行，第1-4行置每個結點為白色，置d【u】為無窮大，每個結點的父母置為NIL，第5行置源結點S為灰色，即意味著過程開始時源結點已被發現。第6行初始化d【s】為0，第7行置源結點的父母結點為NIL，第8行初始化佇列0，使其僅含源結點s，以後Q佇列中僅包含灰色結點的集合。
程式的主循環在9-18行中，只要佇列Q中還有灰色結點，即那些已被發現但還沒有完全搜尋其鄰接表的結點，循環將一直進行下去。第10行確定佇列頭的灰色結點為u。第11-16行的循環考察u的鄰接表中的每一個頂點v。如果v是白色結點，那么該結點還沒有被發現過，算法通過執行第13-16行發現該結點。首先它被置為灰色，距離d【v】置為d【u】+1，而後u被記為該節點的父母，最後它被放在佇列Q的隊尾。當結點u的鄰接表中的所有結點都被檢索後，第17 -18行使u彈出佇列並置成黑色。
