---
title: "06-图"
created: 2026-08-29
tags:
  - 基础与理论
  - 数据结构
  - "408"
---

# 06 图

> 📚 本文是 [[00-数据结构总览|数据结构]] 的第 6 篇，相关系列见 [[00-基础与理论|基础与理论]]。

图 = **多对多的关系**：地图导航、社交网络、编译器依赖分析、任务调度全靠它。408 图论四大件：**存储、遍历、最短路/最小生成树、拓扑排序/关键路径**。本章算法名字多，但骨架只有两句：**DFS 用栈（递归），BFS 用队列**——其余算法都是在这两个骨架上加策略。

## 一、图的基本概念（选择题高发区）

- **有向图/无向图**：边有无方向；有向边 <u,v> 有序，无向边 (u,v) 无序
- **完全图**：无向完全图边数 n(n−1)/2；有向完全图 **n(n−1)**（每个方向一条）
- **顶点的度**：无向图 = 关联边数；有向图 = 入度 + 出度
- **握手定理**：所有顶点度数之和 = **2 × 边数**（每条边贡献两个度）——度数推算的万能钥匙
- **连通**（无向：任意两顶点有路径）/ **强连通**（有向：双向都有路径）
- **生成树**：连通图含全部 n 个顶点的极小连通子图，**n−1 条边**
- 子图、极大连通子图（连通分量）、极小连通子图（生成树）——"极大"vs"极小"别混：**分量求多（极大），生成树求少（极小）**

## 二、存储结构：四选一

| 结构 | 空间 | 适合 | 拿邻接点 |
|---|---|---|---|
| **邻接矩阵** | O(n²)（对称矩阵可压缩，见 [[03-栈与队列\|栈与队列]]） | 稠密图、需要 O(1) 判边 | O(n) 扫一行 |
| **邻接表** | O(n + e) | 稀疏图 | 出边快、**入边慢** |
| 十字链表 | O(n + e) | 有向图（出边入边都快） | 快 |
| 邻接多重表 | O(n + e) | 无向图（每条边只存一份） | 快 |

⚠️ 高频陷阱：**同一个图，邻接表不唯一**（邻接点顺序任意）；**BFS/DFS 序列也因此不唯一**；邻接矩阵唯一。矩阵的行和 = 该点**出度**，列和 = **入度**。

## 三、遍历：BFS 与 DFS

### BFS 广度优先（队列）

```
1. 起点入队并标记
2. 出队访问，未标记的邻接点全部入队并标记
3. 队空为止
```

- **按"层次"扩散**：同一批入队的顶点距起点等远
- **无权图单源最短路**：BFS 天然就是（首次到达 = 最短边数）——这就是 BFS 最重要的隐藏身份
- 复杂度：邻接表 **O(n+e)**，邻接矩阵 O(n²)；辅助空间 O(n)（队列 + 标记数组）

### DFS 深度优先（栈/递归）

```
1. 访问起点，标记
2. 沿未访问邻接点一路扎下去（递归）
3. 走投无路回退一格，换下一个分支
```

- **邻接表 O(n+e)**、邻接矩阵 O(n²)
- 应用：判连通、找环、拓扑排序、求生成树（DFS 树的**回边**是关键：有向图判环 = 遇到"正在访问中"的结点）

⚠️ 408 常考：给邻接表/矩阵，**手写 BFS/DFS 序列**。邻接表要按"题目给定的邻接点顺序"走，别自己排序。

## 四、最小生成树（MST）：贪心两兄弟

带权连通图里，边权和最小的生成树。

| 算法 | 思想 | 适合 | 复杂度 |
|---|---|---|---|
| **Prim** | **从点出发**：每次把"离已建部分最近的一个点"拉进来 | **稠密图**（边多） | O(n²)（邻接矩阵）；堆优化 O(e log n) |
| **Kruskal** | **从边出发**：边按权排序，逐条试放，**不构成环就收** | **稀疏图**（边少） | O(e log e)（并查集判环） |

💡 手算例题（给 5 点 7 边）：按 Kruskal 排序后依次收边，遇到"两端已在同一棵树"的直接跳过——**判环用并查集**（find 父亲相同就跳过，不同就 union）。Prim 则从指定点开始，每轮在"横跨已选点集与未选点集"的边里挑最小。

⚠️ 两者都是贪心，但 MST **整体最优**（贪心选择性质成立）；**MST 不一定唯一**（等权边时），但**权值和唯一**。

## 五、最短路径：Dijkstra 与 Floyd

### Dijkstra 单源最短路（一个起点到全部）

贪心 + 不许有负权边：

```
1. dist[起点]=0，其余 ∞；每轮选未定结点中 dist 最小的 u，标记"已定"
2. 用 u 松弛所有邻居：dist[v] = min(dist[v], dist[u] + w(u,v))
3. 重复 n 轮
```

**手算例题**：v1 起点，边 v1→v2=3, v1→v3=5, v2→v3=1, v2→v4=6, v3→v4=2：

- 第 1 轮：定 v1(0)，松弛 → dist = [_, 3, 5, ∞]
- 第 2 轮：最小 dist 是 v2=3，定 v2，松弛 v3: min(5, 3+1)=4，v4: 3+6=9 → [_, 3, 4, 9]
- 第 3 轮：定 v3=4，松弛 v4: min(9, 4+2)=6 → [_, 3, 4, 6]
- 第 4 轮：定 v4=6 ✅ 最终 v1 到 v4 最短 = **6**（路径 v1→v2→v3→v4）

⚠️ **负权边会让 Dijkstra 错**（已定点的 dist 可能被后续路径推翻）——负权用 **Bellman-Ford**（O(ne)）或 SPFA。OSPF 路由协议（[[04-网络层|网络层]]）用的正是 Dijkstra。

### Floyd 多对多（所有点对）

动态规划：`d[i][j] = min(d[i][j], d[i][k] + d[k][j])`，k 从 1 到 n 三重循环——**O(n³)**，代码五行，负权边也可（但不能有负权环）。适合稠密图全源最短路。

## 六、拓扑排序与关键路径：有向无环图（DAG）

### 拓扑排序（AOV 网：顶点 = 活动）

```
1. 找一个入度为 0 的顶点，输出
2. 删除它及其所有出边
3. 重复；若中途找不到入度 0 点 → 有环，排序失败
```

- 实现：**入度数组 + 队列**（其实就是 BFS 的变体）；也可用 DFS（按完成时间逆序）
- **拓扑序列不唯一**（并列的零入度点顺序随意）；能拓扑排序 ⟺ **有向无环**
- 应用：编译依赖（make/CMake）、课程先修关系

### 关键路径（AOE 网：边 = 活动，顶点 = 事件）

从源点到汇点的**最长路径**——决定整个工程的最短完工时间；关键路径上的活动**不能拖延**。

四个量（408 大题套路）：

| 量 | 含义 | 算法 |
|---|---|---|
| 事件最早发生 ve(j) | 顶点 j 最早何时就绪 | **拓扑序**推进：ve = max(前驱 ve + 边权) |
| 事件最迟 vl(i) | 顶点 i 最晚何时完成 | **逆拓扑序**推进：vl = min(后继 vl − 边权) |
| 活动最早开始 e(i) | 边 <i,j> 的最早开始 | = ve(i) |
| 活动最迟开始 l(i) | 边 <i,j> 的最迟开始 | = vl(j) − w(i,j) |

**关键活动**：e(i) == l(i)（时间余量 = 0）。**缩短关键活动工期才能缩短工期**；但关键路径缩短后可能被次关键路径顶替——大题考点。

## 七、图的应用一张表（面试串讲用）

| 问题 | 算法 | 骨架 |
|---|---|---|
| 无权最短路 | BFS | 队列 |
| 单源带权最短路 | Dijkstra | 贪心 + 优先队列 |
| 全源最短路 | Floyd | 动态规划 |
| 连通最小代价 | Prim / Kruskal | 贪心 |
| 任务依赖 | 拓扑排序 | BFS（入度队列） |
| 工期分析 | 关键路径 | 拓扑 + 逆拓扑 |
| 判环 | DFS 回边 / 并查集 / 拓扑失败 | 栈 |

## 八、盲点自测

1. n 顶点有向完全图几条边？（n(n−1)）
2. 度数之和与边数的关系？（和 = 2e）
3. BFS 为什么能求无权最短路？（按层扩散，首次到达即最少边数）
4. Dijkstra 遇负权为什么错？（"已定"点可能被更短路径推翻）
5. Prim 和 Kruskal 各适合什么图？（稠密/稀疏）
6. 拓扑排序判环的依据？（中途没有入度 0 的点）
7. 关键路径是最长路径还是最短路径？（最长；但它决定工程最短完工时间）
8. 邻接表为什么 BFS/DFS 序列不唯一？（邻接点顺序不唯一）

## 九、动手玩

```python
# 拓扑排序：入度数组 + 队列（背下来就是模板）
from collections import deque

def topo_sort(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == n else None   # None = 有环

print(topo_sort(4, [(0,1),(0,2),(1,3),(2,3)]))   # [0, 1, 2, 3]
print(topo_sort(3, [(0,1),(1,2),(2,0)]))          # None（有环）
```

## 参考资料

- 王道《数据结构考研复习指导》第 6 章
- 《算法图解》第 6、7 章——BFS 和 Dijkstra 的图解版
- [[04-网络层]]——OSPF 用 Dijkstra、RIP 用距离向量：同一套思想在路由协议里
- [[00-刷题理模型|刷题理模型]]——图论题单（岛屿数量、课程表、网络延迟）

⬅️ [[05-树与二叉树|树与二叉树]] 🏠 [[00-基础与理论|00-基础与理论]] ➡️ [[07-查找|查找]]