C# 圖論實作：鄰接表儲存與 DFS/BFS 遍歷完整教學

圖的儲存結構比較

泛型鄰接表實作

using System;
using System.Collections.Generic;

public class AdjacencyList
{
    private readonly List _vertices = new List();

    public void AddVertex(T data)
    {
        if (Contains(data)) throw new ArgumentException("Vertex exists");
        _vertices.Add(new Vertex(data));
    }

    public void AddEdge(T from, T to) // 無向邊
    {
        Vertex f = Find(from) ?? throw new ArgumentException("From not found");
        Vertex t = Find(to) ?? throw new ArgumentException("To not found");
        AddDirectedEdge(f, t);
        AddDirectedEdge(t, f);
    }

    private void AddDirectedEdge(Vertex from, Vertex to)
    {
        if (from.FirstEdge == null) from.FirstEdge = new Node(to);
        else
        {
            Node cur = from.FirstEdge;
            while (cur.Next != null)
            {
                if (cur.AdjVertex.Data.Equals(to.Data))
                    throw new ArgumentException("Edge exists");
                cur = cur.Next;
            }
            cur.Next = new Node(to);
        }
    }

    // ---- 遍歷 ----
    public void DFSTraverse()
    {
        InitVisited();
        foreach (var v in _vertices)
            if (!v.Visited) DFS(v);
    }

    private void DFS(Vertex v)
    {
        v.Visited = true;
        Console.Write(v.Data + " ");
        for (Node n = v.FirstEdge; n != null; n = n.Next)
            if (!n.AdjVertex.Visited) DFS(n.AdjVertex);
    }

    public void BFSTraverse()
    {
        InitVisited();
        foreach (var v in _vertices)
            if (!v.Visited) BFS(v);
    }

    private void BFS(Vertex start)
    {
        var q = new Queue();
        start.Visited = true; Console.Write(start.Data + " "); q.Enqueue(start);
        while (q.Count > 0)
        {
            Vertex v = q.Dequeue();
            for (Node n = v.FirstEdge; n != null; n = n.Next)
                if (!n.AdjVertex.Visited)
                {
                    n.AdjVertex.Visited = true;
                    Console.Write(n.AdjVertex.Data + " ");
                    q.Enqueue(n.AdjVertex);
                }
        }
    }

    private void InitVisited() => _vertices.ForEach(v => v.Visited = false);
    private bool Contains(T data) => _vertices.Exists(v => v.Data.Equals(data));
    private Vertex Find(T data) => _vertices.Find(v => v.Data.Equals(data));

    // 內部類別
    public class Vertex
    {
        public T Data;
        public Node FirstEdge;
        public bool Visited;
        public Vertex(T data) { Data = data; }
    }
    public class Node
    {
        public Vertex AdjVertex;
        public Node Next;
        public Node(Vertex v) { AdjVertex = v; }
    }
}

測試範例與輸出

// 建立圖 8.15
var g = new AdjacencyList();
"V1 V2 V3 V4 V5 V6 V7 V8".Split().ToList().ForEach(g.AddVertex);
g.AddEdge("V1","V2"); g.AddEdge("V1","V3");
g.AddEdge("V2","V4"); g.AddEdge("V2","V5");
g.AddEdge("V3","V6"); g.AddEdge("V3","V7");
g.AddEdge("V4","V8"); g.AddEdge("V5","V8");
g.AddEdge("V6","V8"); g.AddEdge("V7","V8");

Console.Write("DFS: "); g.DFSTraverse(); // V1 V2 V4 V8 V5 V6 V3 V7
Console.Write("\nBFS: "); g.BFSTraverse(); // V1 V2 V3 V4 V5 V6 V7 V8

非連通圖處理

外層 foreach 迴圈配合 Visited 標記，自動處理多連通分量：

public void DFSTraverse()
{
    InitVisited();
    foreach (var v in _vertices)
        if (!v.Visited) DFS(v);
}

帶權圖擴充

在 Node 加入 Weight 欄位即可：

public class Node
{
    public Vertex AdjVertex;
    public Node Next;
    public int Weight; // 權重
    public Node(Vertex v, int w = 0) { AdjVertex = v; Weight = w; }
}

應用場景

• DFS：拓撲排序、強連通分量、尋找路徑、迷宮生成
• BFS：最短路徑（無權圖）、層序遍歷、社交網絡擴散度

總結

鄰接表以 List<Vertex> + 單向鏈表實作，空間效率高、遍歷直觀。DFS 用遞迴/堆疊，BFS 用佇列，配合 Visited 標記即可正確處理環與非連通圖。