資料結構-圖的周遊（類C語言版）

文章目錄

• ​​概念​​

• ​​周遊定義​​
• ​​周遊實質​​
• ​​避免重複通路​​

• ​​深度優先周遊​​

• ​​周遊方法​​
• ​​深度優先搜尋周遊連通圖​​
• ​​深度優先搜尋周遊非連通圖​​
• ​​鄰接矩陣表示的無向圖深度周遊實作​​
• ​​采用鄰接表表示圖的深度優先搜尋周遊​​
• ​​DFS算法效率分析​​

• ​​廣度優先搜尋（Breadth First Search, BFS）​​

• ​​周遊方法​​
• ​​廣度優先搜尋周遊連通圖​​
• ​​BFS算法效率分析​​
• ​​DFS與BFS算法效率比較​​

概念

周遊定義

從已給的連通圖中某一頂點出發，沿着一些邊訪遍圖中所有的頂點， 且使每個頂點僅被通路一次，就叫做圖的周遊，它是圖的基本運算。      

周遊實質

找每個頂點的鄰接點的過程。      

避免重複通路

圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在通路完某個頂點之後可能會沿着某些邊又回到了曾經通路過的頂點。

怎樣避免重複通路？

解決思路：設定輔助數組visited[n]，用來标記每個被通路過的頂點。

• 初始狀态visited[i]為0；
• 頂點 i 被通路，改visited[i]為1，防止被多次通路。

深度優先周遊

周遊方法

• 在通路圖中某一起始頂點v後，由v出發，通路它的任一鄰接頂點w1；
• 再從w1出發，通路與w1鄰接但還未通路過的頂點w1；
• 然後再從w2出發，進行類似的通路，…
• 如此進行下去，直至到達所有的鄰接頂點都被通路過的頂點u為止。

• 接着，退回一步，退到前一次剛通路過的頂點，看是否還有其他沒有被通路的鄰接頂點。

  如果有，則通路此頂點，之後再從此頂點出發，進行與前述類似的通路；

  如果沒有，就再退回一步進行搜尋。重複上述過程，直到連通圖中所有頂點都被通路過位置。

  

  注：連通圖的深度優先周遊類似于樹的先根周遊。

深度優先搜尋周遊連通圖

① 從圖中某個頂點 v 出發， 通路 v, 并置 visited[v]的值為 true。

② 依次檢查 v 的所有鄰接點 w, 如果 visited[w]的值為 false, 再從 w 出發進行遞歸周遊，直到圖中所有頂點都被通路過。

bool visited [MVNum];       // 通路标志數組， 其初值為 "false"
void DFS(Graph G,int v) 
{ // 從第 v 個頂點出發遞歸地深度優先周遊圖G
  cout<<v;visited[v]=true;  // 通路第 v 個頂點， 并置通路标志數組相應分扯值為 true
  for(w=FirstAdjVex(G,v);w>=O;w=NextAdjVex(G,v,w)) 
  // 依次檢查 v 的所有鄰接點 w , FirstAdjVex (G, v)表示 v 的第一個鄰接點
  // NextAdjVex(G,v,w)表示 v 相對千 w 的下一個鄰接點， w≥0表示存在鄰接點
    if(!visited[w]) DFS(G, w);  // 對 v 的尚未通路的鄰接頂點 w 遞歸調用 DFS
}      

深度優先搜尋周遊非連通圖

void DFSTraverse(Graph G) 
{ //對非連通圖G做深度優先周遊
  for(v=O;v<G.vexnum;++v) visited[v]=false;   // 通路标志數組初始化
  for(v=O;v<G.vexnum;++v)           // 循環調用算法[深度優先搜尋周遊連通圖]
  if(!visited[v]) DFS(G,v);           // 對尚未通路的頂點調用DFS
}      

鄰接矩陣表示的無向圖深度周遊實作

// 采用鄰接矩陣表示圖的深度優先搜尋周遊
void DFS_AM(AMGraph G,int v) 
{ // 圖G為鄰接矩陣類型，從第v個頂點出發深度優先搜尋周遊圖G
  cout<<v;visited[v]=true;  // 通路第v個頂點，并置通路标志數組相應分址值為true
  for(w=O;w<G.vexnum;w++)   // 依次檢查鄰接矩陣 v所在的行
    if((G.arcs[v][w] !=O}&&(!visited[w])) DFS(G,w}; 
    // G.arcs[v][w] !=0表示w是v的鄰接點， 如果w未通路， 則遞歸調用DFS
}      

采用鄰接表表示圖的深度優先搜尋周遊

void DFS_AL (ALGraph G,int v) 
{ // 圖G為鄰接表類型， 從第v個頂點出發深度優先搜尋周遊圖G
  cout<<v;visited[v]=true;    // 通路第v個頂點，并置通路标志數組相應分量值為true
  p=G.vertices[v].firstarc;     // p指向v的邊連結清單的第一個邊結點
  while(p!=NULL)          // 邊結點非空
  {
    w=p->adjvex;        // 表示w是v的鄰接點
    if(!visited[w]) DFS(G,w);   // 如果w未通路， 則遞歸調用DFS
    p=p->nextarc;         // p指向下一個邊結點
  }
}      

DFS算法效率分析

• 用鄰接矩陣來表示圖，周遊圖中每一個頂點都要從頭掃描該頂點所在行，時間複雜度為O(n2)。
• 用鄰接表來表示圖，雖然有2e個表結點，但隻需掃描e個結點即可完成周遊，加上通路n個頭結點的時間，時間複雜度為O(n+e)。

結論：

• 稠密圖适于在鄰接矩陣上進行深度周遊；
• 稀疏圖适于在鄰接表上進行深度周遊。

廣度優先搜尋（Breadth First Search, BFS）

周遊方法

廣度優先搜尋周遊連通圖

• 隊頭頂點 u 出隊；
• 依次檢查 u 的所有鄰接點 w, 如果 visited[w]的值為 false, 則通路 w, 并置 visited[w]的值為 true, 然後将 w 進隊。

void BFS{Graph G,int v) 
{ // 按廣度優先非遞歸周遊連通圖G
  count<<v;visited[v]=true;   // 通路第v個頂點，并置通路标志數組相應分址值為true
  InitQueue(Q);         // 輔助隊列Q初始化， 置空
  EnQueue(Q, v);          // v進隊
  while(!QueueEmpty(Q))     // 隊列非空
  {
    DeQueue(Q, u);        // 隊頭元素出隊并置為u
    for(w=FirstAdjVex(G,u);w>=O;w=NextAdjVex(G,u,w)) 
    // 依次檢查u的所有鄰接點w, FirstAdjVex(G,u)表示u的第一個鄰接點
    // NextAdjVex(G,u,w)表示u相對于w的下一個鄰接點，w≥0表示存在鄰接點
      if(!visited[w])     // w為u的尚未通路的鄰接頂點
      {
        cout<<w; visited[w]=true;   // 通路 w, 并置通路标志數組相應分扯值為true
        EnQueue(Q, w);    // w進隊
      }
  }
}      

BFS算法效率分析

• 如果使用鄰接矩陣，則BFS對于每一個被通路到的頂點，都要循環檢測矩陣中的整整一行（n個元素），總的時間代價為O(n2)。
• 用鄰接表來表示圖，雖然有2e個表結點，但隻需掃描e個結點即可完成周遊，加上通路n個頭結點的時間，時間複雜度為O(n+e)。

DFS與BFS算法效率比較

• 空間複雜度相同，都是O(n)（借用了堆棧或隊列）；
• 時間複雜度隻與存儲結構（鄰接矩陣或鄰接表）有關，而與搜尋路徑無關。