C#图的邻接矩阵与邻接表表示（小白也能看懂的图数据结构教程）

什么是图？

图由顶点（Vertex）和边（Edge）组成。例如，城市之间的航班可以看作一个图：每个城市是一个顶点，每条航线是一条边。

根据边是否有方向，图可分为有向图和无向图；根据边是否带有权重，又可分为带权图和无权图。本文主要讨论无权无向图的基本表示方法。

1. 邻接矩阵（Adjacency Matrix）

邻接矩阵使用一个二维数组来表示图。假设图中有 n 个顶点，我们就创建一个 n × n 的矩阵。如果顶点 i 和顶点 j 之间有边，则 matrix[i][j] = 1；否则为 0。

优点：查询两个顶点是否相连的时间复杂度是 O(1)。
缺点：空间复杂度高，为 O(n²)，即使图很稀疏（边很少）也会浪费大量空间。

C# 实现邻接矩阵

using System;class GraphMatrix{    private int[,] matrix;    private int vertexCount;    public GraphMatrix(int vertices)    {        vertexCount = vertices;        matrix = new int[vertices, vertices];    }    // 添加边    public void AddEdge(int u, int v)    {        if (u < vertexCount && v < vertexCount)        {            matrix[u, v] = 1;            matrix[v, u] = 1; // 无向图，对称        }    }    // 打印邻接矩阵    public void PrintMatrix()    {        for (int i = 0; i < vertexCount; i++)        {            for (int j = 0; j < vertexCount; j++)            {                Console.Write(matrix[i, j] + " ");            }            Console.WriteLine();        }    }}// 使用示例class Program{    static void Main()    {        GraphMatrix g = new GraphMatrix(4);        g.AddEdge(0, 1);        g.AddEdge(1, 2);        g.AddEdge(2, 3);        g.PrintMatrix();    }}

2. 邻接表（Adjacency List）

邻接表使用一个数组（或列表），其中每个元素对应一个顶点，并存储该顶点的所有相邻顶点。通常用 List<List<int>> 或 Dictionary<int, List<int>> 来实现。

优点：节省空间，尤其适合稀疏图（边远少于顶点数平方的情况）。
缺点：判断两个顶点是否相连需要遍历邻接表，时间复杂度为 O(degree)，不如邻接矩阵快。

C# 实现邻接表

using System;using System.Collections.Generic;class GraphList{    private Dictionary<int, List<int>> adjList;    public GraphList()    {        adjList = new Dictionary<int, List<int>>();    }    // 添加顶点    public void AddVertex(int vertex)    {        if (!adjList.ContainsKey(vertex))        {            adjList[vertex] = new List<int>();        }    }    // 添加边    public void AddEdge(int u, int v)    {        AddVertex(u);        AddVertex(v);        adjList[u].Add(v);        adjList[v].Add(u); // 无向图    }    // 打印邻接表    public void PrintGraph()    {        foreach (var kvp in adjList)        {            Console.Write($"顶点 {kvp.Key}: ");            Console.WriteLine(string.Join(", ", kvp.Value));        }    }}// 使用示例class Program{    static void Main()    {        GraphList g = new GraphList();        g.AddEdge(0, 1);        g.AddEdge(1, 2);        g.AddEdge(2, 3);        g.PrintGraph();    }}

如何选择？

- 如果你的图是稠密图（边很多，接近完全图），推荐使用 C#图的邻接矩阵。
- 如果你的图是稀疏图（边很少），或者顶点数量很大，推荐使用 C#图的邻接表。

在实际开发中，图的数据结构C# 实现常用于算法题、游戏开发、网络拓扑分析等领域。掌握这两种表示方法，是学习更高级图算法（如 DFS、BFS、Dijkstra 等）的基础。

总结

本文详细讲解了在 C# 中如何用 邻接矩阵 和 邻接表 表示图，并提供了完整的可运行代码。无论你是初学者还是有一定经验的开发者，理解这两种 C#图表示方法 都能帮助你更好地处理图相关问题。

动手试试吧！修改代码，添加更多功能（比如删除边、判断连通性等），加深理解。