熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

圖 - 圖的遍歷 - 廣度優先遍歷 (二)

2013-11-15 15:42:41  來源: 數據結構 

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

  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
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.