C#與數據結構--圖的遍歷(5)

圖的廣度優先搜索遍歷算法是一個分層遍歷的過程，和二叉樹的廣度優先搜索遍歷類同。它從圖的某一頂點Vi出發，訪問此頂點後，依次訪問Vi的各個未曾訪問過的鄰接點，然後分別從這些鄰接點出發，直至圖中所有已有已被訪問的頂點的鄰接點都被訪問到。對於圖8.15所示的無向連通圖，若頂點Vi為初始訪問的頂點，則廣度優先搜索遍歷頂點訪問順序是：V1 → V2 → V3 → V4 → V5 → V6 → V7 → V8。遍歷過程如圖8.16的所示。

和二叉樹的廣度優先搜索遍歷類似，圖的廣度優先搜索遍歷也需要借助隊列來完成，例8.3演示了這個過程。

【例8-3 BFSTraverse.cs】廣度優先搜索遍歷

打開【例8-2 DFSTraverse.cs】，在AdjacencyList<T>類中添加以下代碼後，將文件另存為BFSTraverse.cs。

54      public void BFSTraverse() //廣度優先遍歷
55      {
56          InitVisited(); //將visited標志全部置為false
57          BFS(items[0]); //從第一個頂點開始遍歷
58      }
59      private void BFS(Vertex<T> v) //使用隊列進行廣度優先遍歷
60      {   //創建一個隊列
61          Queue<Vertex<T>> queue = new Queue<Vertex<T>>();
62          Console.Write(v.data + " "); //訪問
63          v.visited = true; //設置訪問標志
64          queue.Enqueue(v); //進隊
65          while (queue.Count > 0) //只要隊不為空就循環
66          {
67              Vertex<T> w = queue.Dequeue();
68              Node node = w.firstEdge;
69              while (node != null) //訪問此頂點的所有鄰接點
70              {   //如果鄰接點未被訪問，則遞歸訪問它的邊
71                  if (!node.adjvex.visited)
72                  {
73                      Console.Write(node.adjvex.data + " "); //訪問
74                      node.adjvex.visited = true; //設置訪問標志
75                      queue.Enqueue(node.adjvex); //進隊
76                  }
77                  node = node.next; //訪問下一個鄰接點
78              }
79          }
80      }

【例8-3 Demo8-3.cs】廣度優先搜索遍歷測試

using System;
class Demo8_3
{
    static void Main(string[] args)
    {
        AdjacencyList<string> a = new AdjacencyList<string>();
        a.AddVertex("V1");
        a.AddVertex("V2");
        a.AddVertex("V3");
        a.AddVertex("V4");
        a.AddVertex("V5");
        a.AddVertex("V6");
        a.AddVertex("V7");
        a.AddVertex("V8");
        a.AddEdge("V1", "V2");
        a.AddEdge("V1", "V3");
        a.AddEdge("V2", "V4");
        a.AddEdge("V2", "V5");
        a.AddEdge("V3", "V6");
        a.AddEdge("V3", "V7");
        a.AddEdge("V4", "V8");
        a.AddEdge("V5", "V8");
        a.AddEdge("V6", "V8");
        a.AddEdge("V7", "V8");
        a.BFSTraverse(); //廣度優先搜索遍歷
    }
}

運行結果：

V1 V2 V3 V4 V5 V6 V7 V8

運行結果請參照圖8.16進行分析。