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

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

　　void BFSM(MGraph *Gint k)

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

　　int ij;

　　CirQueue Q;

　　InitQueue(&Q);

　　printf(visit vertex%cG>vexs[k]); //訪問源點v k

　　visited[k]=TRUE;

　　EnQueue(&Qk);

　　while(!QueueEmpty(&Q)){

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

　　for(j=;jn;j++)//依次搜索v i 的鄰接點v j

　　if(G>edges[i][j]==&&!visited[j]){//v i 未訪問

　　printf(visit vertex%cG>vexs[j]);//訪問v i

　　visited[j]=TRUE;

　　EnQueue(&Qj);//訪問過的v i 人隊

　　}

　　}//endwhile

　　}//BFSM

　　() 廣度優先遍歷算法

　　類似於DFSTraverse【參見DFSTraverse算法】

　　圖的廣度優先遍歷序列

　　廣度優先遍歷圖所得的頂點序列定義為圖的廣度優先遍歷序列簡稱BFS序列

　　()一個圖的BFS序列不是惟一的

　　()給定了源點及圖的存儲結構時算法BFS和BFSM所給出BFS序列就是惟一的

　　【例】下圖中G 以鄰接矩陣為存儲結構以v 為出發點的BFS搜索過程【 參見動畫演示 】和BFS序列為V V V V

　　 V V V V

　　

　　【例】上圖中G 以鄰接表為存儲結構以v 為出發點的BFS搜索過程和BFS序列【 參見動畫演示 】

　　算法分析

　　對於具有n個頂點和e條邊的無向圖或有向圖每個頂點均入隊一次廣度優先遍歷(BFSTraverse)圖的時間復雜度和

　　DFSTraverse算法相同

　　當圖是連通圖時BFSTraverse算法只需調用一次BFS或BFSM即可完成遍歷操作此時BFS和BFSM的時間復雜度分別為O(n+e)和

　　(n )

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