C#无向图数据结构实现与基础算法解析

叶初

发布时间：2026-10-16 | 3人浏览过

原创

本文介绍在 C# 中构建无向图的高效方法，重点讲解基于邻接表的数据结构设计，以及如何利用深度优先搜索（DFS）和广度优先搜索（BFS）解决图的连通性、路径查找等核心算法问题。

1. 无向图的基本概念与术语

图由一组顶点和连接这些顶点的边组成。为了高效处理，通常使用 0 至 V-1 的整数索引来表示图中的各个顶点。v-w 记法表示连接顶点 v 和 w 的无向边。在绘制时，虽然直观上常用圆圈和线段表示，但数据的拓扑结构才是核心。

特殊结构与术语定义

自环：一条连接一个顶点和其自身的边；
平行边：连接同一对顶点的两条边，含有平行边的图称为多重图，否则为简单图；
相邻与度数：通过边相连的顶点互为相邻，依附于某顶点的边的总数即为该顶点的度数；
路径与环：路径是由边顺序连接的一系列顶点。起点和终点相同的简单路径称为环。如果图中任意两顶点间存在路径，则称它们是连通的。

判断一幅图是否为树的依据包括：含有 V - 1 条边且不含有环、是连通的且删除任意一条边会断开连通性等五个等价条件。

2. 无向图的数据结构表示

在 C# 中实现图处理 API 时，需平衡空间占用与操作速度。常见的表示方法有邻接矩阵、边数组和邻接表数组。对于稀疏图，标准做法是使用邻接表。

邻接表数组实现 (Adjacency List)

使用一个以顶点为索引的列表数组，每个元素指向一个包含该顶点所有相邻顶点的链表（或列表）。这种结构的性能优势在于：

空间复杂度与 V + E 成正比；
添加一条边只需常数时间；
遍历某顶点的所有相邻顶点所需时间与它的度数成正比。

具体实现逻辑是将 w 添加到 v 的邻接表中，同时将 v 添加到 w 的邻接表中，确保每条边存储两次。

C# 邻接表完整实现

public class Graph
{
    private int v;
    private int e;
    private List<int>[] adj; //邻接表(用List 代替 bag)

    public Graph(int V)
    {
        v = V;
        e = 0;
        adj = new List<int>[V];
        for (var i = 0; i < V; i++)
            adj[i] = new List<int>();
    }

    public void AddEdge(int v, int w)
    {
        adj[v].Add(w);
        adj[w].Add(v);
        e++;
    }

    public IEnumerable<int> Adj(int v)
    {
        return adj[v];
    }
}

此外，还可以通过 Degree() 和 AvgDegree() 等静态方法计算顶点的度数和平均度数，以及统计自环数量。

3. 深度优先搜索 (DFS)

深度优先搜索是处理图的基础算法，旨在找到从起点到所有其他顶点的连通路径。其核心思想是利用递归：访问一个顶点后，将其标记为已访问，然后递归地访问其未被标记的邻居。

实现步骤

1. 创建一个布尔数组 marked[] 记录顶点是否被访问。 2. 从起点开始调用递归函数 Dfs(G, s)。 3. 在每个递归层级中，遍历当前顶点的邻接表，对未访问的邻居继续调用 Dfs。

public class DepthFirstSearch
{
    private bool[] marked;
    private int count;

    public DepthFirstSearch(Graph G,int s)
    {
        marked = new bool[G.V()];
        Dfs(G,s);
    }

    private void Dfs(Graph g, int V)
    {
        marked[V] = true;
        count++;
        foreach (var w in g.Adj(V))
        {
            if (!marked[w])
                Dfs(g,w);
        }
    }

    public bool Marked(int w) => marked[w];
}

该方法可用于解决连通性问题以及查找单点路径，其运行时间与顶点的度数之和成正比。

4. 寻找路径与广度优先搜索 (BFS)

深度优先路径查找

如果需要返回具体的路径序列，可以在 DFS 的基础上维护一个 edgeTo[] 数组。当首次发现顶点 w 时，记录 edgeTo[w] = v，这实际上构建了一棵以起点为根的树。回溯路径时，从目标点沿 edgeTo 逆向追踪至起点。

广度优先搜索：最短路径首选

深度优先搜索得到的路径不一定是最短的。若要寻找边数最少的最短路径，应使用广度优先搜索（BFS）。BFS 使用队列（Queue）而非栈，它按距离起点的远近层次进行遍历：首先访问所有距离为 1 的邻居，然后是距离为 2 的邻居，以此类推。

BFS 的核心逻辑是非递归的：

1. 将起点加入队列并标记。

2. 当队列非空时，取出队首顶点 v。

3. 遍历 v 的所有相邻顶点，若未标记，则更新 edgeTo，标记并入队。

public class BreadthFirstPaths
{
    private bool[] marked;
    private int[] edgeTo;
    private int s;

    public BreadthFirstPaths(Graph G,int s)
    {
        marked = new bool[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        Bfs(G,s);
    }

    private void Bfs(Graph G, int s)
    {
        Queue<int> queue = new Queue<int>();
        marked[s] = true;
        queue.Enqueue(s);
        while (queue.Count > 0)
        {
            int v = queue.Dequeue();
            foreach (var w in G.Adj(v))
            {
                if (!marked[w])
                {
                    edgeTo[w] = v;
                    marked[w] = true;
                    queue.Enqueue(w);
                }
            }
        }
    }
}

BFS 保证了找到的第一条路径即为最短路径（不含权重的无向图），最坏情况下的时间复杂度与 V + E 成正比。