廣度優先遍歷

廣度優先遍歷是連通圖的一種遍歷策略。因為它的思想是從一個頂點V0開始，輻射狀地優先遍歷其周圍較廣的區域，故得名。

基本介紹

• 中文名：廣度優先遍歷
• 外文名：breadth-first traverse
• 實質：一種遍歷策略
• 優點：輻射狀地優先遍歷
• 特性：廣度優先生成樹
• 思想：從一個頂點V0開始

基本思想

1、從圖中某個頂點V0齣發，並訪問此頂點；

2、從V0齣發，訪問V0的各個未曾訪問的鄰接點W1，W2，…,Wk;然後,依次從W1,W2,…,Wk出發訪問各自未被訪問的鄰接點；

3、重複步驟2，直到全部頂點都被訪問為止。

性質

與深度優先遍歷類似，廣度優先遍歷也有許多有用的特性：

1、廣度優先生成樹

在廣度優先遍歷中，如果將每次“前進”（縱深）路過的（將被訪問的）結點和邊都記錄下來，就得到一個子圖，該子圖為以出發點為根的樹，稱為廣度優先生成樹。這種情況與深度優先遍歷類似。

類似地，也可以給廣度優先生成樹結點定義時間戳。

2、最短路徑

顯然，從v0齣發廣度優先遍歷圖，將得到v0到它的各個可達到的路徑。我們這裡定義路徑上的邊的數目為路徑長度。與深度優先遍歷不同，廣度優先遍歷得到的v0到各點的路徑是最短路徑（未考慮邊權）。

算法

template <int max_size>

void Digraph<max_size> ::

breadth_first(void (*visit)(Vertex &)) const

/* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order.

Uses: Methods of class Queue. */

{

Queue q;

bool visited [max_size];

Vertex v, w, x;

for (all v in G) visited [v] = false;

for (all v in G)

if (!visited [v]) {

q.append (v);

while (!q.empty ( )){

q.retrieve (w);

if (!visited [w]) {

visited [w] = true; (*visit) (w);

for (all x adjacent to w) q.append (x); }

q.serve ( ); } }

}

廣度優先搜尋算法pascal 算法框架

Program BFS;

初始化，存儲初始狀態（記錄初始結點）；

設佇列首指針closed=0；佇列尾指針open：=1；

repeat

首指針closed後移一格，取其所指向的結點；

for r:=1 to max_r do

begin

if子結點符合條件 且 子結點沒有重複擴展 then

begin

尾指針open加1；把新結點存入佇列尾；

記錄相關信息；

if 達到目標 then 輸出且結束；

end;

until closed>=open(佇列空)

深度比較

廣度優先遍歷與深度優先遍歷的區別在於：廣度優先遍歷是以層為順序，將某一層上的所有節點都搜尋到了之後才向下一層搜尋；而深度優先遍歷是將某一條枝椏上的所有節點都搜尋到了之後，才轉向搜尋另一條枝椏上的所有節點。

深度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出剛訪問這個結點的第一個未被訪問的鄰結點，然後再以此鄰結點為頂點，繼續找它的下一個新的頂點進行訪問，重複此步驟，直到所有結點都被訪問完為止。

廣度優先遍歷從某個頂點出發，首先訪問這個頂點，然後找出這個結點的所有未被訪問的鄰接點，訪問完後再訪問這些結點中第一個鄰接點的所有結點，重複此方法，直到所有結點都被訪問完為止。

可以看到兩種方法最大的區別在於前者從頂點的第一個鄰接點一直訪問下去再訪問頂點的第二個鄰接點；後者從頂點開始訪問該頂點的所有鄰接點再依次向下，一層一層的訪問。

報告

調試

一、佇列操作中，若佇列中只有一個元素，刪除隊頭元素時產生錯誤。原因是程式中沒有考慮這種特殊的情況。修改後，佇列的刪除操作運作正常。

二、在求圖的第u個頂點，與其相鄰的一系列頂點中，第w個頂點的下一個頂點時，若是求最後一個頂點的下一個頂點時，函式進入了死循環。原因是判斷條件沒有寫好，造成了判斷值恆為真，因此進入了死循環。修改後，函式正常運行。

三、廣度優先遍歷圖的時候，是從指定的任一頂點開始遍歷，當遇到該圖為無向非連通圖，並不能把該圖遍歷。

原因是沒有寫出一個循環體，去嘗試遍歷其他沒有被遍歷的頂點。加上這樣一個循環體後，便可以遍歷任意一種圖了，並且還可以在此基礎上算出圖的兩通分量。

四、在輸入圖信息的時候，若輸入非法字元，程式會異常終止。例如程式要求輸入一個整型，用戶卻輸入了一個字母，這時候會出現異常。只是程式是否健壯性的一個體現。採用輸入流的一些函式，便可以解決這一問題。還有其他一些類似的輸入異常，都是採用類似的處理方法。

五．作為一個完整的程式，友好的界面是必須的。因ci(no chinese input)程式中適當地採用系統中的清屏命令，使得界面更加簡潔·明了。

運行結果

一、輸入圖的頂點數：a，運行結果：非法輸入，請重新輸入。

二、確定第1個頂點與第2個頂點是否有關係時，輸入非0和1，運行結果：程式並不回響。

三、確定從第幾個頂點開始遍歷該圖是，輸入：j，r，ab，-1，0，1，21.

四、運行結果：非法輸入，請重新輸入。