圖 - 圖的遍歷 - 廣度優先遍歷 （一）

　　廣度優先遍歷(BreadthFirstTraversal)

　　廣度優先遍歷的遞歸定義

　　設圖G的初態是所有頂點均未訪問過在G中任選一頂點v為源點則廣度優先遍歷可以定義為首先訪問出發點v接著依次訪問

　　v的所有鄰接點w w …w t 然後再依次訪問與w l w …w t 鄰接的所有未曾訪問過的頂點依此類推直至

　　圖中所有和源點v有路徑相通的頂點都已訪問到為止此時從v開始的搜索過程結束

　　若G是連通圖則遍歷完成;否則在圖C中另選一個尚未訪問的頂點作為新源點繼續上述的搜索過程直至G中所有頂點均已被訪

　　問為止

　　廣度優先遍歷類似於樹的按層次遍歷采用的搜索方法的特點是盡可能先對橫向進行搜索故稱其為廣度優先搜索(Breadth

　　FirstSearch)相應的遍歷也就自然地稱為廣度優先遍歷

　　廣度優先搜索過程

　　在廣度優先搜索過程中設x和y是兩個相繼要被訪問的未訪問過的頂點它們的鄰接點分別記為x x …x s 和y

　　y …y t

　　為確保先訪問的頂點其鄰接點亦先被訪問在搜索過程中使用FIFO隊列來保存已訪問過的頂點當訪問x和y時這兩個頂點相繼

　　入隊此後當x和y相繼出隊時我們分別從x和y出發搜索其鄰接點x x …x s 和y y …y t 對其中未訪

　　者進行訪問並將其人隊這種方法是將每個已訪問的頂點人隊故保證了每個頂點至多只有一次人隊

　　廣度優先搜索算法

　　()鄰接表表示圖的廣度優先搜索算法

　　void BFS(ALGraph*Gint k)

　　{// 以v k 為源點對用鄰接表表示的圖G進行廣度優先搜索

　　int i;

　　CirQueue Q; //須將隊列定義中DataType改為int

　　EdgeNode *p;

　　InitQueue(&Q);//隊列初始化

　　//訪問源點v k

　　printf(visit vertex%eG>adjlist[k]vertex);

　　visited[k]=TRUE;

　　EnQueue(&Qk);//v k 已訪問將其人隊(實際上是將其序號人隊)

　　while(!QueueEmpty(&Q)){//隊非空則執行

　　i=DeQueue(&Q); //相當於v i 出隊

　　p=G>adjlist[i]firstedge; //取v i 的邊表頭指針

　　while(p){//依次搜索v i 的鄰接點v j (令p>adjvex=j)

　　if(!visited[p>adivex]){ //若v j 未訪問過

　　printf(visitvertex%cC>adjlistlp>adjvex]vertex); //訪問v j

　　visited[p>adjvex]=TRUE;

　　EnQueue(&Qp>adjvex);//訪問過的v j 人隊

　　}//endif

　　p=p>next;//找v i 的下一鄰接點

　　}//endwhile

　　}//endwhile

　　}//end of BFS

From:http://tw.wingwit.com/Article/program/sjjg/201311/23834.html