Appearance
邻接表
为什么需要邻接表
邻接矩阵用二维数组存储图，空间复杂度为 O(V²)。当图是稀疏图（边数远小于 V²）时，矩阵中大量元素为 0，造成严重的空间浪费。
邻接表的思路是：只存储实际存在的边，用一个顶点数组 + 若干条边链表来表示图，空间复杂度降为 O(V+E)。408 考研中，邻接表是图的两大核心存储结构之一，需要与邻接矩阵对比掌握。
核心思想
邻接表由两部分组成：
- 顶点数组：长度为 V 的数组，每个元素存储顶点信息及一个指向边链表的头指针
- 边链表：每个顶点对应一条单链表，链表中的每个结点表示一条从该顶点出发的边
结构示意：
顶点数组 边链表
[0] V₀ → (1) → (3) → NULL
[1] V₁ → (0) → (2) → NULL
[2] V₂ → (1) → NULL
[3] V₃ → (0) → NULL有向图 vs 无向图：
- 有向图：边
<Vi, Vj>只在 Vi 的边链表中存储一次 - 无向图：边
(Vi, Vj)需要在 Vi 和 Vj 的边链表中各存储一次，因此边结点总数为 2E
交互可视化
通过下方的交互动画，你可以逐步观察邻接表的执行过程：
操作详解
存储结构
邻接表的 C 语言定义：
c
#define MaxVertexNum 100
// 边结点
typedef struct ArcNode {
int adjvex; // 该边指向的顶点编号
struct ArcNode *next; // 指向下一条边的指针
// int weight; // 带权图可加权值字段
} ArcNode;
// 顶点结点
typedef struct VNode {
char data; // 顶点数据
ArcNode *first; // 指向第一条边的指针
} VNode, AdjList[MaxVertexNum];
// 邻接表存储的图
typedef struct {
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数、边数
} ALGraph;度的计算：
- 无向图：顶点 Vi 的度 = Vi 边链表的结点个数
- 有向图：Vi 边链表的结点个数只是出度；计算入度需要遍历所有顶点的边链表，统计指向 Vi 的边数
为了方便求入度，可以建立逆邻接表：对每个顶点 Vi，将所有指向 Vi 的边组成链表。逆邻接表中 Vi 的链表长度即为 Vi 的入度。
邻接矩阵与邻接表互转
邻接矩阵 → 邻接表：遍历矩阵第 i 行，若 A[i][j] = 1，则在顶点 i 的边链表中插入结点 j。
cpp
// 邻接矩阵转邻接表（头插法）
void MatToList(int A[][MaxVertexNum], ALGraph &G) {
for (int i = 0; i < G.vexnum; i++) {
G.vertices[i].first = NULL;
for (int j = G.vexnum - 1; j >= 0; j--) {
if (A[i][j] == 1) {
ArcNode *p = new ArcNode;
p->adjvex = j;
p->next = G.vertices[i].first;
G.vertices[i].first = p;
}
}
}
}邻接表 → 邻接矩阵：遍历每个顶点的边链表，将对应位置置 1。
cpp
void ListToMat(ALGraph G, int A[][MaxVertexNum]) {
// 初始化矩阵为 0
for (int i = 0; i < G.vexnum; i++)
for (int j = 0; j < G.vexnum; j++)
A[i][j] = 0;
// 遍历邻接表填充矩阵
for (int i = 0; i < G.vexnum; i++) {
ArcNode *p = G.vertices[i].first;
while (p) {
A[i][p->adjvex] = 1;
p = p->next;
}
}
}优缺点分析
| 对比项 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间复杂度 | O(V²) | O(V+E) |
| 适用场景 | 稠密图 | 稀疏图 |
| 判断边是否存在 | O(1)，直接访问 A[i][j] | O(V)，需遍历链表 |
| 求顶点的度 | O(V)，遍历一行/列 | 出度 O(度)，入度 O(V+E) |
| 增/删边 | O(1) | O(1) 插入 / O(度) 删除 |
| 表示唯一性 | 唯一 | 不唯一（链表结点顺序可变） |
复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 建立邻接表 | O(V+E) | 遍历所有顶点和边各一次 |
| 判断边 (Vi, Vj) | O(度(Vi)) | 遍历 Vi 的边链表 |
| 求顶点出度 | O(度(Vi)) | 遍历 Vi 的边链表 |
| 求顶点入度 | O(V+E) | 需遍历所有边链表 |
| BFS/DFS 遍历 | O(V+E) | 每个顶点和边各访问一次 |
空间复杂度：O(V+E)。无向图边结点数为 2E，有向图边结点数为 E，加上 V 个顶点结点。
考研高频考点
- ⭐ 邻接表的存储结构定义及画图（选择题/综合题高频）
- ⭐ 邻接表 vs 邻接矩阵的对比（简答题必考）
- ⭐ 无向图边结点数为 2E（选择题/填空题陷阱）
- ⭐ 有向图中出度与入度的计算方法及逆邻接表（选择题）
- 邻接表的表示不唯一性（概念题）
- 基于邻接表的 BFS/DFS 时间复杂度 O(V+E)（分析题）