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

8.3.1深度優先搜索遍歷

圖的深度優先搜索遍歷類似於二叉樹的深度優先搜索遍歷。其基本思想如下：假定以圖中某個頂點Vi為出發點，首先訪問出發點，然後選擇一個Vi的未訪問過的鄰接點Vj，以Vj為新的出發點繼續進行深度優先搜索，直至圖中所有頂點都被訪問過。顯然，這是一個遞歸的搜索過程。

現以圖8.15為例說明深度優先搜索過程。假定V1是出發點，首先訪問V1。因V1有兩個鄰接點V2、V3均末被訪問過，可以選擇V2作為新的出發點，訪問V2之後，再找V2的末訪問過的鄰接點。同V2鄰接的有V1、V4和V5，其中V1已被訪問過，而V4、V5尚未被訪問過，可以選擇V4作為新的出發點。重復上述搜索過程，繼續依次訪問V8、V5 。訪問V5之後，由於與V5相鄰的頂點均已被訪問過，搜索退回到V8，訪問V8的另一個鄰接點V6。接下來依次訪問V3和V7，最後得到的的頂點的訪問序列為：V1 → V2 → V4 → V8 → V5 → V6 → V3 → V7。

下面根據上一節創建的鄰接表存儲結構添加深度優先搜索遍歷代碼。

【例8-2 DFSTraverse.cs】深度優先搜索遍歷

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

35      public void DFSTraverse() //深度優先遍歷
36      {
37          InitVisited(); //將visited標志全部置為false
38          DFS(items[0]); //從第一個頂點開始遍歷
39      }
40      private void DFS(Vertex<T> v) //使用遞歸進行深度優先遍歷
41      {
42          v.visited = true; //將訪問標志設為true
43          Console.Write(v.data + " "); //訪問
44          Node node = v.firstEdge;
45          while (node != null) //訪問此頂點的所有鄰接點
46          {   //如果鄰接點未被訪問，則遞歸訪問它的邊
47              if (!node.adjvex.visited)
48              {
49                  DFS(node.adjvex); //遞歸
50              }
51              node = node.next; //訪問下一個鄰接點
52          }
53      }

98 private void InitVisited() //初始化visited標志

99 {

100 foreach (Vertex<T> v in items)

101 {

102 v.visited = false; //全部置為false

103 }

104 }

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

using System;
class Demo8_2
{
    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.DFSTraverse();
    }
}

運行結果：

V1 V2 V4 V8 V5 V6 V3 V7

本例參照圖8-15進行設計，運行過程請參照對圖8-15所作的分析。