C# 資料結構 - 圖的廣度優先搜尋 (BFS) 實作 (5)

8.3.2 廣度優先搜尋遍歷

分層遍歷：從起始頂點 Vi 訪問其所有未訪問鄰接點，再從這些鄰接點繼續，直到所有鄰接點被訪問。需輔助佇列。

圖 8.15 無向連通圖 BFS 訪問順序：V1 → V2 → V3 → V4 → V5 → V6 → V7 → V8

鄰接表 BFS 程式碼

public void BFSTraverse()
{
    InitVisited();
    BFS(items[0]);
}

private void BFS(Vertex<T> v)
{
    Queue<Vertex<T>> queue = new Queue<Vertex<T>>();
    Console.Write(v.data + " ");
    v.visited = true;
    queue.Enqueue(v);
    while (queue.Count > 0)
    {
        Vertex<T> w = queue.Dequeue();
        Node node = w.firstEdge;
        while (node != null)
        {
            if (!node.adjvex.visited)
            {
                Console.Write(node.adjvex.data + " ");
                node.adjvex.visited = true;
                queue.Enqueue(node.adjvex);
            }
            node = node.next;
        }
    }
}

測試結果

var a = new AdjacencyList<string>();
// 加入 V1~V8 及邊...
a.BFSTraverse();
// 輸出: V1 V2 V3 V4 V5 V6 V7 V8