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

AdjacencyList<T>類使用泛型實現了圖的鄰接表存儲結構。它包含兩個內部類，Vertex<Tvalue>類（109～118行代碼）用於表示一個表頭結點，Node類（99～107）則用於表示表結點，其中存放著鄰接點信息，用來表示表頭結點的某條邊。多個Node用next指針相連形成一個單鏈表，表頭指針為Vertex類的firstEdge成員，表頭結點所代表的頂點的所有邊的信息均包含在鏈表內，其結構如圖8.12所示。所不同之處在於：

l　Vertex類中包含了一個visited成員，它的作用是在圖遍歷時標識當前節點是否被訪問過，這一點在稍後會講到。

l　鄰接點指針域adjvex直接指向某個表頭結點，而不是表頭結點在數組中的索引。

AdjacencyList<T>類中使用了一個泛型List代替數組來保存表頭結點信息（第5行代碼），從而不再考慮數組存儲空間不夠的情況發生，簡化了操作。

由於一條無向邊的信息需要在邊的兩個頂點分別存儲信息，即添加兩個有向邊，所以58～78行代碼的私有方法AddDirectedEdge()方法用於添加一個有向邊。新的鄰接點信息即可以添加到鏈表的頭部也可以添加到尾部，添加到鏈表頭部可以簡化操作，但考慮到要檢查是否添加了重復邊，需要遍歷整個鏈表，所以最終把鄰接點信息添加到鏈表尾部。

【例8-1 Demo8-1.cs】圖的鄰接表存儲結構測試

using System;
class Demo8_1
{
    static void Main(string[] args)
    {
        AdjacencyList<char> a = new AdjacencyList<char>();
        //添加頂點
        a.AddVertex('A');
        a.AddVertex('B');
        a.AddVertex('C');
        a.AddVertex('D');
        //添加邊
        a.AddEdge('A', 'B');
        a.AddEdge('A', 'C');
        a.AddEdge('A', 'D');
        a.AddEdge('B', 'D');
        Console.WriteLine(a.ToString());
    }
}

運行結果：

A：BCD

B：AD

C：A

D：AB

本例存儲的表如圖8.12所示，結果中，冒號前面的是表頭結點，冒號後面的是鏈表中的表結點。

8.3 圖的遍歷

和樹的遍歷類似，在此，我們希望從圖中某一頂點出發訪遍圖中其余頂點，且使每一個頂點僅被訪問一次，這一過程就叫做圖的遍歷(TraversingGraph)。如果只訪問圖的頂點而不關注邊的信息，那麼圖的遍歷十分簡單，使用一個foreach語句遍歷存放頂點信息的數組即可。但如果為了實現特定算法，就需要根據邊的信息按照一定順序進行遍歷。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。

圖的遍歷要比樹的遍歷復雜得多，由於圖的任一頂點都可能和其余頂點相鄰接，故在訪問了某頂點之後，可能順著某條邊又訪問到了已訪問過的頂點，因此，在圖的遍歷過程中，必須記下每個訪問過的頂點，以免同一個頂點被訪問多次。為此給頂點附設訪問標志visited，其初值為false，一旦某個頂點被訪問，則其visited標志置為true。

圖的遍歷方法有兩種：一種是深度優先搜索遍歷（Depth-First Search 簡稱DFS）；另一種是廣度優先搜索遍歷（Breadth_First Search 簡稱BFS）。