C#图的邻接表存储优化（高效实现图结构与性能提升技巧）

基础实现：使用 Dictionary + List

在 C# 中，最直观的邻接表实现方式是使用 Dictionary<T, List<T>>。其中，键表示图中的顶点，值是一个列表，包含该顶点的所有邻居。

public class Graph<T>{    private Dictionary<T, List<T>> adjacencyList;    public Graph()    {        adjacencyList = new Dictionary<T, List<T>>();    }    public void AddVertex(T vertex)    {        if (!adjacencyList.ContainsKey(vertex))        {            adjacencyList[vertex] = new List<T>();        }    }    public void AddEdge(T from, T to)    {        AddVertex(from);        AddVertex(to);        adjacencyList[from].Add(to);        // 如果是无向图，还需添加反向边        // adjacencyList[to].Add(from);    }    public List<T> GetNeighbors(T vertex)    {        return adjacencyList.ContainsKey(vertex) ? adjacencyList[vertex] : new List<T>();    }}

邻接表优化策略

虽然上述实现简单易懂，但在实际项目中可能存在性能或内存浪费的问题。以下是几种常见的邻接表优化方法：

1. 使用 HashSet 替代 List（避免重复边）

如果图中不允许存在重复边（例如大多数实际应用场景），使用 HashSet<T> 可以自动去重，并且查找、插入、删除操作的时间复杂度为 O(1)。

private Dictionary<T, HashSet<T>> adjacencyList;public void AddEdge(T from, T to){    AddVertex(from);    AddVertex(to);    adjacencyList[from].Add(to); // 自动忽略重复添加}

2. 预分配顶点 ID（整型索引优化）

如果你的图顶点数量固定且可枚举（如城市编号、用户ID等），可以将顶点映射为整数索引，使用 List<List<int>> 或 List<HashSet<int>> 存储邻接关系。这样可以避免哈希计算开销，提升缓存局部性。

public class IndexedGraph{    private List<HashSet<int>> adjacencyList;    private int vertexCount;    public IndexedGraph(int n)    {        vertexCount = n;        adjacencyList = new List<HashSet<int>>(n);        for (int i = 0; i < n; i++)        {            adjacencyList.Add(new HashSet<int>());        }    }    public void AddEdge(int from, int to)    {        if (from < vertexCount && to < vertexCount)        {            adjacencyList[from].Add(to);        }    }}

3. 内存池与对象复用（适用于高频图操作）

在需要频繁创建/销毁图结构的场景（如游戏AI路径搜索），可以考虑使用对象池技术复用邻接表容器，减少 GC 压力。

总结

通过合理选择数据结构（如 HashSet）、使用整型索引、以及引入内存优化策略，我们可以显著提升 C#图的邻接表存储 的性能和内存效率。无论你是初学者还是有经验的开发者，掌握这些 C#数据结构 和 图算法实现 技巧，都将为你解决复杂问题打下坚实基础。

希望这篇教程能帮助你理解 邻接表优化 的核心思想，并在实际项目中灵活应用。动手试试吧！