图解数据结构：5分钟搞懂图的邻接矩阵与邻接表区别
在计算机科学中，图是一种非常重要的非线性数据结构，它由顶点（Vertex）和边（Edge）组成，能够表示多对多的复杂关系。图的存储方式直接影响算法的效率和资源消耗，其中邻接矩阵和邻接表是最常用的两种存储结构。本文将用直观的对比方式，帮助读者快速理解这两种存储方式的本质区别。
1. 图的存储结构概述
图结构在现实世界中有广泛的应用场景，比如社交网络中的好友关系、交通网络中的路线规划、编译器中的控制流分析等。选择合适的存储结构需要考虑以下几个关键因素：
- 顶点数量：大规模图和小规模图对存储的需求不同
- 边的密度：稀疏图和稠密图的存储效率差异显著
- 操作需求：频繁查询还是频繁修改
- 内存限制：存储空间是否有限制
邻接矩阵和邻接表正是针对这些不同需求而设计的两种经典存储方案。下面我们通过具体例子来理解它们的实现原理。
2. 邻接矩阵：直观的二维数组表示
邻接矩阵使用一个二维数组来表示图中顶点之间的连接关系。对于包含n个顶点的图，邻接矩阵是一个n×n的方阵。
2.1 邻接矩阵的实现原理
#define MAX_VERTEX 100 typedef struct { int vertex[MAX_VERTEX]; // 顶点数组 int matrix[MAX_VERTEX][MAX_VERTEX]; // 邻接矩阵 int vertexNum, edgeNum; // 顶点数和边数 } AdjMatrixGraph;对于无权图，矩阵中的元素值为：
- 1：表示顶点i和j之间有边相连
- 0：表示顶点i和j之间没有边相连
对于带权图（网），矩阵元素存储的是边的权值，通常用特殊值（如INT_MAX）表示无边。
2.2 邻接矩阵的优缺点分析
优点：
- 查询速度快：判断两个顶点是否相邻只需O(1)时间
- 实现简单：二维数组直观易懂
- 适合稠密图：当边数接近顶点数的平方时，空间利用率高
缺点：
- 空间复杂度高：需要O(V²)的存储空间，V为顶点数
- 添加/删除顶点成本高：需要重新调整矩阵大小
- 稀疏图浪费空间：当边数远小于顶点数时，矩阵中大部分元素为0
提示：邻接矩阵特别适合需要频繁判断顶点间是否存在边的场景，如路径查找算法。
3. 邻接表：灵活的链式存储结构
邻接表采用数组+链表的方式存储图结构，每个顶点对应一个链表，存储其所有邻接顶点。
3.1 邻接表的实现原理
typedef struct EdgeNode { int adjvex; // 邻接顶点下标 int weight; // 边权重（可选） struct EdgeNode *next; // 指向下一个邻接点 } EdgeNode; typedef struct { char data; // 顶点数据 EdgeNode *firstEdge; // 边表头指针 } VertexNode; typedef struct { VertexNode adjList[MAX_VERTEX]; // 邻接表 int vertexNum, edgeNum; // 顶点数和边数 } AdjListGraph;3.2 邻接表的优缺点分析
优点：
- 空间效率高：只存储实际存在的边，空间复杂度为O(V+E)
- 适合稀疏图：边数较少时节省大量空间
- 易于添加顶点：扩展性强，添加新顶点方便
缺点：
- 查询效率较低：判断两顶点是否相邻需要遍历链表，最坏O(V)
- 实现较复杂：需要处理指针和动态内存分配
- 不适合频繁判断邻接关系：相比矩阵效率较低
4. 邻接矩阵与邻接表的性能对比
| 特性 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V+E) |
| 查询边存在 | O(1) | O(V) |
| 添加顶点 | O(V²) | O(1) |
| 添加边 | O(1) | O(1) |
| 删除边 | O(1) | O(V) |
| 遍历邻接点 | O(V) | O(degree(V)) |
| 适合图类型 | 稠密图 | 稀疏图 |
从表中可以看出，两种存储结构各有优劣，实际应用中需要根据具体场景选择：
- 社交网络：通常选择邻接表，因为社交关系通常是稀疏的
- 交通网络：可能选择邻接矩阵，因为城市之间的连接相对密集
- 路径规划：邻接矩阵更适合频繁的邻接关系查询
5. 实际应用中的选择建议
在实际开发中，选择图的存储结构需要考虑以下几个因素：
- 图的规模：对于顶点数超过10000的大规模图，邻接表通常是更好的选择
- 边的密度：边数接近V²时选择邻接矩阵，边数远小于V²时选择邻接表
- 硬件限制：内存有限的嵌入式系统可能更倾向于邻接表
- 算法需求：某些算法对存储结构有特定要求
// 邻接表添加边的示例代码 void addEdge(AdjListGraph *G, int v1, int v2, int weight) { EdgeNode *e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = v2; e->weight = weight; e->next = G->adjList[v1].firstEdge; G->adjList[v1].firstEdge = e; // 无向图需要添加反向边 e = (EdgeNode*)malloc(sizeof(EdgeNode)); e->adjvex = v1; e->weight = weight; e->next = G->adjList[v2].firstEdge; G->adjList[v2].firstEdge = e; }在项目实践中，我曾经遇到一个需要处理百万级顶点图的问题。最初使用邻接矩阵导致内存溢出，切换到邻接表后不仅解决了内存问题，还因为数据局部性更好而提升了缓存命中率，整体性能反而有所提升。
