C# 資料結構 - 圖的深度優先搜尋 (DFS) 實作 (4)

8.3.1 深度優先搜尋遍歷

圖的 DFS 類似二元樹，從起始頂點出發，遞迴訪問未訪問過的鄰接點，直到所有頂點被訪問。

範例圖遍歷過程

以 V1 為起點，訪問序列：V1 → V2 → V4 → V8 → V5 → V6 → V3 → V7

鄰接表結構 DFS 程式碼

public void DFSTraverse() // 深度優先遍歷
{
    InitVisited();           // 重設 visited 標記
    DFS(items[0]);           // 從第一個頂點開始
}

private void DFS(Vertex<T> v)
{
    v.visited = true;
    Console.Write(v.data + " ");
    Node node = v.firstEdge;
    while (node != null)
    {
        if (!node.adjvex.visited)
            DFS(node.adjvex); // 遞迴
        node = node.next;
    }
}

private void InitVisited()
{
    foreach (Vertex<T> v in items) v.visited = false;
}

測試程式與結果

var a = new AdjacencyList<string>();
a.AddVertex("V1"); ... a.AddVertex("V8");
a.AddEdge("V1", "V2"); ... a.AddEdge("V7", "V8");
a.DFSTraverse();
// 輸出: V1 V2 V4 V8 V5 V6 V3 V7