图
6.1 图的基本概念
图（Graph）是由顶点集合 V 和边集合 E 组成的数据结构，记为 G = (V, E)。图中顶点之间是多对多的关系。
基本术语：
| 术语 | 定义 |
|---|---|
| 有向图 | 边有方向，用尖括号 <v, w> 表示 |
| 无向图 | 边无方向，用圆括号 (v, w) 表示 |
| 完全图 | 任意两顶点间都有边。无向完全图边数 n(n-1)/2，有向完全图边数 n(n-1) |
| 子图 | 原图的顶点和边的子集构成的图 |
| 连通图 | 无向图中任意两个顶点都有路径相连 |
| 连通分量 | 无向图的极大连通子图 |
| 强连通图 | 有向图中任意两个顶点互相可达 |
| 强连通分量 | 有向图的极大强连通子图 |
| 度 | 无向图中一个顶点关联的边数 |
| 入度/出度 | 有向图中指向/指出该顶点的边数 |
| 生成树 | 连通图的极小连通子图，含 n 个顶点 n-1 条边 |
| 网 | 带权值的图（加权图） |
| 路径 | 从一个顶点到另一个顶点的顶点序列 |
| 路径长度 | 路径上边的数目（无权图）或权值之和（带权图） |
| 回路/环 | 第一个顶点和最后一个顶点相同的路径 |
💡 记忆技巧：图和树的区别在于——树没有回路，图可以有回路。"树是一张简化的图"。
6.2 图的存储结构
邻接矩阵
用二维数组表示图中顶点间的邻接关系。
typedef struct {
int vertices[MAXV]; // 顶点表
int edges[MAXV][MAXV]; // 邻接矩阵
int n, e; // 顶点数和边数
} MGraph;
- 无向图的邻接矩阵是对称矩阵。
- 有向图的邻接矩阵不一定对称。
- 空间复杂度 O(n²)，适合稠密图。
- 判断两顶点是否邻接只需 O(1)。
邻接表
用顺序存储顶点 + 链式存储出边（或无向图的边）。
typedef struct ArcNode {
int adjvex; // 邻接顶点下标
struct ArcNode *nextarc;
InfoType info; // 边的权值等信息
} ArcNode;
typedef struct VNode {
VertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAXV];
typedef struct {
AdjList vertices;
int n, e;
} ALGraph;
- 空间复杂度 O(n + e)，适合稀疏图。
- 容易得到顶点的出度（遍历链表），入度需要遍历整个邻接表（有向图时）。
十字链表（有向图）
把邻接表和逆邻接表合并为一个结构。每个顶点有一个入弧链表和出弧链表。每个弧结点包含弧尾、弧头、同弧尾的下一条弧、同弧头的下一条弧。
优点：容易获取出度和入度。空间复杂度 O(n + e)。
邻接多重表（无向图）
每条边只存储一次，一个边结点同时出现在两个顶点的链表中。解决了邻接表存储无向图时边重复存储的问题。
📌 408考点提示：邻接矩阵和邻接表的对比是常考选择题。十字链表和邻接多重表了解概念即可。
6.3 图的遍历
深度优先搜索（DFS）
类似树的先序遍历，使用栈（递归栈）。
void DFS(ALGraph G, int v) {
visited[v] = true;
visit(v);
for (ArcNode *p = G.vertices[v].firstarc; p; p = p->nextarc) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
}
}
- 时间复杂度：邻接表 O(n + e)，邻接矩阵 O(n²)。
- 适用于求解连通分量、检测环、拓扑排序等。
广度优先搜索（BFS）
类似树的层序遍历，使用队列。
void BFS(ALGraph G, int v) {
Queue Q;
InitQueue(Q);
visited[v] = true;
visit(v);
EnQueue(Q, v);
while (!QueueEmpty(Q)) {
DeQueue(Q, v);
for (ArcNode *p = G.vertices[v].firstarc; p; p = p->nextarc) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = true;
visit(p->adjvex);
EnQueue(Q, p->adjvex);
}
}
}
}
- 时间复杂度：邻接表 O(n + e)，邻接矩阵 O(n²)。
- 适用于求最短路径（无权图）、最小生成树。
💡 记忆技巧：BFS 用队列——"广度"意味着"一层一层来"；DFS 用栈——"深度"意味着"一条路走到黑"再回溯。
6.4 最小生成树（MST）
Prim算法
从一个顶点开始，每次选择连接已选顶点集合和未选顶点集合的最小权值边。
- 时间复杂度：O(n²)（邻接矩阵），适合稠密图。
- 与边数无关，只与顶点数有关。
过程示例：
从 A 开始：
A-B:6, A-C:1, A-D:5 → 选 A-C(1)
C-B:5, C-D:4 → 选 C-D(4) 或 C-B(5) → 选 C-D(4)
D-B:2 → 选 D-B(2)
→ MST: A-C(1), C-D(4), D-B(2)，总权值=7
Kruskal算法
每次选择最小权值边，若不构成回路则加入。
- 时间复杂度：O(e log e)（取决于排序），适合稀疏图。
- 需要判断是否构成回路，用并查集实现。
对比 Prim 和 Kruskal：
| 算法 | 策略 | 时间复杂度 | 适合场景 |
|---|---|---|---|
| Prim | 选顶点 | O(n²) | 稠密图 |
| Kruskal | 选边 | O(e log e) | 稀疏图 |
6.5 最短路径
Dijkstra算法（单源最短路径）
从源点出发，每次选择距离源点最近的未确定顶点，更新其邻接顶点的距离。
void Dijkstra(MGraph G, int v0) {
int dist[MAXV], path[MAXV];
bool final[MAXV] = {false};
// 初始化
for (int i = 0; i < G.n; i++) {
dist[i] = G.edges[v0][i];
path[i] = (dist[i] < INF) ? v0 : -1;
}
final[v0] = true;
// 循环 n-1 次
for (int k = 1; k < G.n; k++) {
int min = INF, u = -1;
for (int i = 0; i < G.n; i++)
if (!final[i] && dist[i] < min) {
min = dist[i]; u = i;
}
if (u == -1) break;
final[u] = true;
for (int i = 0; i < G.n; i++)
if (!final[i] && dist[u] + G.edges[u][i] < dist[i]) {
dist[i] = dist[u] + G.edges[u][i];
path[i] = u;
}
}
}
- 时间复杂度 O(n²)。
- 不适用于有负权边的图。
📌 408考点提示：Dijkstra 算法的中间过程表是高频题型，需要手动填写每一轮的 dist 和 path 数组变化。
Floyd算法（多源最短路径）
void Floyd(MGraph G) {
int A[MAXV][MAXV], path[MAXV][MAXV];
for (int i = 0; i < G.n; i++)
for (int j = 0; j < G.n; j++) {
A[i][j] = G.edges[i][j];
path[i][j] = -1;
}
for (int k = 0; k < G.n; k++)
for (int i = 0; i < G.n; i++)
for (int j = 0; j < G.n; j++)
if (A[i][j] > A[i][k] + A[k][j]) {
A[i][j] = A[i][k] + A[k][j];
path[i][j] = k;
}
}
- 时间复杂度 O(n³)。
- 可以处理负权边（但不能有负权回路）。
6.6 拓扑排序
拓扑排序是对有向无环图（DAG）的顶点的一种排序，使得对于每一条有向边 <u, v>，u 都在 v 之前出现。
算法步骤：
- 从图中选择一个入度为 0 的顶点输出。
- 删除该顶点及其所有出边（邻接顶点入度减 1）。
- 重复直到所有顶点输出（排完）或没有入度为 0 的顶点（有环）。
应用：AOV 网的工程顺序安排。
⚠️ 易错点：拓扑排序的结果不唯一——多个入度为 0 的顶点时，选择顺序不同会导致不同的结果。
6.7 关键路径（AOE网）
AOE 网（Activity On Edge）用顶点表示事件，有向边表示活动，边的权值表示活动持续时间。
四个关键量：
| 参数 | 含义 | 计算方法 |
|---|---|---|
| ve(k) | 事件 k 的最早发生时间 | ve(j) = max{ve(i) + w(i,j)} |
| vl(k) | 事件 k 的最迟发生时间 | vl(i) = min{vl(j) - w(i,j)} |
| e(i) | 活动 i 的最早开始时间 | e(i) = ve(活动起点) |
| l(i) | 活动 i 的最迟开始时间 | l(i) = vl(活动终点) - w(i) |
关键活动：d(i) = l(i) - e(i) = 0 的活动。 关键路径：所有关键活动构成的路径。关键路径可能不止一条。
💡 记忆技巧：最早时间"从上到下求最大"，最迟时间"从下到上求最小"。
6.8 题型示例
例题1：给定有向图的邻接矩阵，画出其邻接表，写出 DFS 和 BFS 序列（从顶点 0 开始）。
假设有向图有 5 个顶点 0~4，邻接矩阵中 M[i][j]=1 表示有边 i→j：
0 1 2 3 4
0 0 1 1 0 0
1 0 0 0 1 0
2 0 0 0 1 1
3 0 0 0 0 1
4 0 0 0 0 0
DFS 序列（从 0 开始）：0→1→3→4→2（访问完 1 的邻接后回到 0 访问 2） BFS 序列（从 0 开始）：0→1→2→3→4
例题2：使用 Dijkstra 算法求从顶点 A 到其他各顶点的最短路径。
假设有向带权图，A~E 五个顶点，邻接矩阵如下（∞ 表示不通）：
A B C D E
A 0 4 2 ∞ ∞
B ∞ 0 1 5 ∞
C ∞ ∞ 0 8 10
D ∞ ∞ ∞ 0 2
E ∞ ∞ ∞ ∞ 0
Dijkstra 求解过程（从 A 出发）：
| 轮次 | 选择 | dist[B] | dist[C] | dist[D] | dist[E] |
|---|---|---|---|---|---|
| 初态 | — | A→B=4 | A→C=2 | ∞ | ∞ |
| 1 | C | A→C(2) | — | A→C→D=10 | A→C→E=12 |
| 2 | B | — | — | A→B→D=9 | — |
| 3 | D | — | — | — | A→D→E=11 |
| 4 | E | — | — | — | — |
最终结果：
- A→B: 4 (A→B)
- A→C: 2 (A→C)
- A→D: 9 (A→B→D)
- A→E: 11 (A→B→D→E) 或 (A→C→D→E) 但 取小值
例题3：求 AOE 网的关键路径。
有 6 个事件（顶点 1~6），活动（有向边）及其权值：
1→2(3) 1→3(2) 2→4(2) 3→4(4)
3→5(3) 4→5(1) 4→6(5) 5→6(2)
解：
-
正向求 ve： ve(1)=0 ve(2)=max(0+3)=3 ve(3)=max(0+2)=2 ve(4)=max(3+2, 2+4)=6 ve(5)=max(2+3, 6+1)=7 ve(6)=max(6+5, 7+2)=11
-
反向求 vl： vl(6)=11 vl(5)=min(11-2)=9 vl(4)=min(11-5, 9-1)=6 vl(3)=min(6-4, 9-3)=2 vl(2)=min(6-2)=4 vl(1)=min(4-3, 2-2)=0
-
求各活动的 e、l：
活动 e l l-e
1→2 0 4-3=1 1
1→3 0 2-2=0 0 ←关键
2→4 3 6-2=4 1
3→4 2 6-4=2 0 ←关键
3→5 2 9-3=6 4
4→5 6 9-1=8 2
4→6 6 11-5=6 0 ←关键
5→6 7 11-2=9 2
- 关键活动：1→3, 3→4, 4→6 关键路径：1→3→4→6，长度=2+4+5=11
本章总结
图的算法是 408 中难度较高但也是必考的部分。重点掌握：DFS/BFS 的遍历过程、Prim 和 Kruskal 构造最小生成树的过程、Dijkstra 和 Floyd 求最短路径的过程、拓扑排序以及关键路径的计算。这些算法多数会出现在选择题或综合题中，需要能手算模拟全过程。