第11章 图论基础¶
图（Graph） 是算法竞赛中出现频率最高的数据结构之一。从最短路到网络流，从拓扑排序到强连通分量，图论贯穿了整个竞赛生涯。本章将系统讲解图的基本概念、存储方式、遍历算法，以及最短路、最小生成树、拓扑排序、并查集等核心内容。
11.1 图的基本概念¶
11.1.1 图的定义¶
图 \(G = (V, E)\) 由两个集合组成：
- 顶点集（Vertex Set） \(V\)：图中所有节点的集合，\(|V| = n\) 表示节点数。
- 边集（Edge Set） \(E\)：图中所有边的集合，\(|E| = m\) 表示边数。
11.1.2 有向图与无向图¶
| 类型 | 边的表示 | 示例 | 实际含义 |
|---|---|---|---|
| 无向图 | \((u, v)\) 表示 \(u\) 与 \(v\) 之间的边 | 社交网络中的好友关系 | 双向通行 |
| 有向图 | \(\langle u, v \rangle\) 表示从 \(u\) 到 \(v\) 的有向边 | 网页间的超链接 | 单向通行 |
11.1.3 度¶
- 无向图的度：节点 \(v\) 的度 \(deg(v)\) 是与 \(v\) 相连的边数。
- 有向图的度：分为 入度（\(indeg(v)\)，指向 \(v\) 的边数）和 出度（\(outdeg(v)\)，从 \(v\) 出发的边数）。
- 握手定理：无向图中所有节点的度之和等于边数的两倍，即 \(\sum_{v \in V} deg(v) = 2m\)。
11.1.4 连通性¶
- 连通图（无向）：任意两个节点之间都存在路径。
- 强连通图（有向）：任意两个节点之间都存在有向路径。
- 弱连通图（有向）：忽略方向后为连通图。
- 连通分量：无向图中的极大连通子图。
11.1.5 路径与环¶
- 路径（Path）：从节点 \(u\) 到节点 \(v\) 的一个节点序列，其中相邻节点之间有边相连。简单路径要求所有节点互不相同。
- 环（Cycle）：起点与终点相同的路径。简单环要求除起点和终点外其余节点互不相同。
- 有向无环图（DAG）：不存在环的有向图，是拓扑排序的前提。
11.1.6 图的分类示意¶
graph TD
A[图] --> B[按方向]
A --> C[按边权]
A --> D[按连通性]
B --> B1[无向图]
B --> B2[有向图]
C --> C1[无权图]
C --> C2[带权图]
D --> D1[连通图]
D --> D2[非连通图]
D --> D3[强连通图]11.1.7 常见术语图示¶
graph LR
A --- B
B --- C
C --- D
D --- A
B --- D
E --- F
style E fill:#f9f,stroke:#333
style F fill:#f9f,stroke:#333上图展示了：左侧 \(A, B, C, D\) 构成一个连通分量，包含环 \(A \to B \to D \to A\)；右侧 \(E, F\) 构成另一个连通分量。整个图是非连通图，有两个连通分量。
11.2 图的存储¶
11.2.1 邻接矩阵¶
邻接矩阵 使用一个二维数组 g[i][j] 存储节点 \(i\) 到节点 \(j\) 的边权信息。
// 邻接矩阵存储
const int MAXN = 1005;
int g[MAXN][MAXN];
// 初始化（无权图：0表示无边，1表示有边；带权图：INF表示无边）
memset(g, 0x3f, sizeof(g)); // 初始化为无穷大
// 添加无向边
void addEdge(int u, int v, int w) {
g[u][v] = w;
g[v][u] = w; // 有向图去掉这一行
}
// 添加有向边
void addDirectedEdge(int u, int v, int w) {
g[u][v] = w;
}
适用场景：
| 优点 | 缺点 |
|---|---|
| 查询两点间是否有边 \(O(1)\) | 空间 \(O(n^2)\)，稠密图浪费 |
| 实现简单 | 遍历某点所有邻居需要 \(O(n)\) |
| 适合稠密图（\(m \approx n^2\)） | 不适合稀疏图（\(m \ll n^2\)） |
11.2.2 邻接表¶
邻接表 使用 vector 数组，每个节点维护一个链表存储其所有邻居。
// 无权图邻接表
vector<int> adj[MAXN];
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // 有向图去掉这一行
}
// 带权图邻接表
struct Edge {
int to, weight;
};
vector<Edge> adj[MAXN];
void addEdge(int u, int v, int w) {
adj[u].push_back({v, w});
adj[v].push_back({u, w}); // 有向图去掉这一行
}
// 遍历节点u的所有邻居
for (auto& e : adj[u]) {
// e.to 是邻居节点, e.weight 是边权
}
复杂度对比：
| 操作 | 邻接矩阵 | 邻接表 |
|---|---|---|
| 空间 | \(O(n^2)\) | \(O(n + m)\) |
| 判断 \((u,v)\) 是否有边 | \(O(1)\) | \(O(deg(u))\) |
| 遍历 \(u\) 的所有邻居 | \(O(n)\) | \(O(deg(u))\) |
| 添加一条边 | \(O(1)\) | \(O(1)\) |
竞赛推荐：绝大多数题目使用邻接表（
vector<Edge>），在 \(n\) 很大（\(>5000\)）时邻接矩阵会 MLE。
11.2.3 链式前向星¶
链式前向星 是一种静态链表存储方式，兼具邻接表的空间效率和数组的访问速度，在早期竞赛中广泛使用。
核心思想： 用数组模拟链表。每条边有一个 next 指针，指向同一起点的下一条边。head[u] 指向节点 \(u\) 的第一条边。
struct Edge {
int to, next, weight;
} e[MAXM];
int head[MAXN], cnt;
void init() {
memset(head, -1, sizeof(head));
cnt = 0;
}
void addEdge(int u, int v, int w) {
e[++cnt] = {v, head[u], w};
head[u] = cnt;
}
// 遍历节点u的所有邻居
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
int w = e[i].weight;
// 处理边 (u, v, w)
}
存储原理：
graph LR
subgraph "head[] 数组"
H2["head[2] -> 2"]
H4["head[4] -> 4"]
end
subgraph "e[] 边数组"
E1["e[1]: to=4, next=-1"]
E2["e[2]: to=3, next=1"]
E3["e[3]: to=2, next=-1"]
E4["e[4]: to=1, next=3"]
end
H2 --> E2
E2 --> E1
H4 --> E4
E4 --> E3假设添加了边：(2,4), (2,3), (4,2), (4,1)。则：
head[2] = 2，即e[2]是节点 2 的第一条边（to=3），e[2].next = 1指向e[1]（to=4），e[1].next = -1结束。head[4] = 4，即e[4]是节点 4 的第一条边（to=1），e[4].next = 3指向e[3]（to=2），e[3].next = -1结束。
三种存储方式总结：
| 方式 | 空间 | 实现难度 | 适用场景 |
|---|---|---|---|
| 邻接矩阵 | \(O(n^2)\) | 简单 | 小规模稠密图 |
| 邻接表 (vector) | \(O(n + m)\) | 简单 | 大多数竞赛题首选 |
| 链式前向星 | \(O(n + m)\) | 中等 | 对常数要求极高时 |
11.3 图的遍历¶
11.3.1 DFS 遍历¶
深度优先搜索（DFS） 沿着一条路径尽可能深地探索，直到无路可走时回溯。
vector<int> adj[MAXN];
bool vis[MAXN];
void dfs(int u) {
vis[u] = true;
for (int v : adj[u]) {
if (!vis[v]) {
dfs(v);
}
}
}
时间复杂度： \(O(n + m)\)
递归层数问题： 当图的深度很大（如链状图 \(n=10^5\)）时，递归 DFS 可能栈溢出。解决方法：
// 方法1：手动扩栈（注意：此写法是 MSVC 专用的链接器指令，
// GNU G++ 下无效！Linux 评测机可在本地用 ulimit -s unlimited 调栈，
// 若评测环境栈空间受限，最稳妥的做法是改用下面的迭代式 DFS）
#pragma comment(linker, "/STACK:1024000000,1024000000")
// 方法2：迭代式DFS（用栈模拟）
void dfs_iterative(int start) {
stack<int> st;
st.push(start);
vis[start] = true;
while (!st.empty()) {
int u = st.top();
st.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
st.push(v);
}
}
}
}
11.3.2 BFS 遍历¶
广度优先搜索（BFS） 从起点开始，逐层向外扩展，保证第一次到达每个节点时经过的路径是最短的（在无权图中）。
void bfs(int start) {
queue<int> q;
vector<int> dist(n + 1, -1);
dist[start] = 0;
q.push(start);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
q.push(v);
}
}
}
}
时间复杂度： \(O(n + m)\)
BFS 的性质： 在无权图中，BFS 天然求出从起点到所有节点的最短路径（边数最少）。这是因为 BFS 按层遍历，先到达的节点距离更近。
11.3.3 连通分量计数¶
使用 DFS 或 BFS 可以方便地计算无向图的连通分量个数：
int countComponents(int n) {
int cnt = 0;
vector<bool> vis(n + 1, false);
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
cnt++;
// BFS标记整个连通分量
queue<int> q;
q.push(i);
vis[i] = true;
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : adj[u]) {
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
}
return cnt;
}
技巧：并查集也可以高效处理连通分量问题，详见 11.7 节。
11.4 最短路¶
最短路问题是图论中最经典的问题之一。根据问题规模和边权特征，选择合适的算法至关重要。
graph TD
A[最短路问题] --> B{单源还是多源?}
B -->|单源| C{有负权边?}
B -->|多源| D[Floyd 全源最短路]
C -->|无负权| E{稀疏图还是稠密图?}
C -->|有负权| F{是否有负环?}
E -->|稀疏 m~n| G[Dijkstra 堆优化]
E -->|稠密 m~n^2| H[Dijkstra 朴素]
F -->|无负环| I[Bellman-Ford / SPFA]
F -->|有负环| J[问题无解]11.4.1 Dijkstra 算法¶
贪心思想¶
Dijkstra 算法基于贪心策略：每次选择当前距离起点最近的未确定节点，用它来更新其邻居的距离。
核心原理： 当一个节点 \(u\) 被选中时（即 \(dist[u]\) 最小），\(dist[u]\) 已经是最终的最短距离。因为所有未确定的节点距离都 \(\geq dist[u]\)，不可能通过它们找到更短的路径到 \(u\)。
算法图解¶
graph TD
subgraph "第1步: 初始状态"
A1((A: 0)) -->|4| B1((B: INF))
A1 -->|2| C1((C: INF))
C1 -->|1| B1
B1 -->|5| D1((D: INF))
end
subgraph "第2步: 选A, 更新B=4, C=2"
A2((A: 确定)) -->|4| B2((B: 4))
A2 -->|2| C2((C: 2确定))
C2 -->|1| B2
B2 -->|5| D2((D: INF))
end
subgraph "第3步: 选C, 更新B=3"
A3((A)) -->|4| B3((B: 3确定))
A3 -->|2| C3((C))
C3 -->|1| B3
B3 -->|5| D3((D: 8确定))
end朴素版 Dijkstra¶
适用于稠密图，时间复杂度 \(O(n^2 + m)\)。
const int INF = 0x3f3f3f3f;
const int MAXN = 5005;
struct Edge {
int to, w;
};
vector<Edge> adj[MAXN];
int dist[MAXN];
bool vis[MAXN];
int n, m;
void dijkstra(int s) {
memset(dist, 0x3f, sizeof(dist));
memset(vis, false, sizeof(vis));
dist[s] = 0;
for (int i = 1; i <= n; i++) {
// 找未确定节点中距离最小的
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
if (dist[u] == INF) break; // 剩余节点不可达
vis[u] = true;
// 用u更新邻居
for (auto& e : adj[u]) {
if (dist[e.to] > dist[u] + e.w) {
dist[e.to] = dist[u] + e.w;
}
}
}
}
堆优化版 Dijkstra¶
适用于稀疏图，使用优先队列（小根堆），时间复杂度 \(O(m \log n)\)。
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w;
};
vector<Edge> adj[MAXN];
int dist[MAXN];
int n, m;
void dijkstra(int s) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
// pair<距离, 节点>，小根堆
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d > dist[u]) continue; // 懒删除：跳过已确定的节点
for (auto& e : adj[u]) {
if (dist[e.to] > dist[u] + e.w) {
dist[e.to] = dist[u] + e.w;
pq.push({dist[e.to], e.to});
}
}
}
}
关键点：
if (d > dist[u]) continue这行"懒删除"非常重要。因为优先队列中同一个节点可能被多次插入，我们只处理第一次弹出（即最短距离）的那次。
11.4.2 Bellman-Ford 算法¶
适用场景： 存在负权边的图。
核心思想： 对所有边进行 \(n - 1\) 轮松弛操作。可以归纳证明：进行 \(k\) 轮松弛后，所有最短路径边数 \(\leq k\) 的结点已求出正确值；由于任意最短路径至多含 \(n - 1\) 条边，故至多 \(n - 1\) 轮即收敛。
struct Edge {
int u, v, w;
};
vector<Edge> edges;
int dist[MAXN];
int n, m;
bool bellmanFord(int s) {
memset(dist, 0x3f, sizeof(dist));
dist[s] = 0;
for (int i = 1; i <= n - 1; i++) { // 至多 n-1 轮
bool updated = false;
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
dist[e.v] = dist[e.u] + e.w;
updated = true;
}
}
if (!updated) break; // 无更新说明已收敛
}
// 检测负环：再松弛一轮，如果还能更新则存在负环
for (auto& e : edges) {
if (dist[e.u] < INF && dist[e.v] > dist[e.u] + e.w) {
return false; // 存在负环
}
}
return true;
}
时间复杂度： \(O(nm)\)
负环检测： 如果第 \(n\) 轮松弛仍然有更新，则说明存在负权环（负环）。因为正常情况下 \(n - 1\) 轮即可收敛。
11.4.3 SPFA 算法¶
SPFA（Shortest Path Faster Algorithm） 是 Bellman-Ford 的队列优化版本。
核心思想： 只有被更新过的节点才需要去更新其邻居，用队列维护这些"活跃"节点。
const int INF = 0x3f3f3f3f;
struct Edge {
int to, w;
};
vector<Edge> adj[MAXN];
int dist[MAXN];
bool inq[MAXN]; // 是否在队列中
int cnt[MAXN]; // 入队次数，用于判负环
int n, m;
bool spfa(int s) {
memset(dist, 0x3f, sizeof(dist));
memset(inq, false, sizeof(inq));
memset(cnt, 0, sizeof(cnt));
dist[s] = 0;
queue<int> q;
q.push(s);
inq[s] = true;
cnt[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
inq[u] = false;
for (auto& e : adj[u]) {
if (dist[e.to] > dist[u] + e.w) {
dist[e.to] = dist[u] + e.w;
if (!inq[e.to]) {
q.push(e.to);
inq[e.to] = true;
if (++cnt[e.to] > n) {
return false; // 存在负环
}
}
}
}
}
return true;
}
时间复杂度： 平均 \(O(km)\)（\(k\) 为小常数），最坏 \(O(nm)\)。
注意：SPFA 在稠密图上可能退化到 \(O(nm)\)，与朴素 Bellman-Ford 相同。如果题目数据没有负权边，强烈建议使用 Dijkstra，因为出题人可能会构造卡 SPFA 的数据。
11.4.4 Floyd 算法¶
适用场景： 求所有节点对之间的最短路（全源最短路），\(n \leq 500\) 左右。
核心思想： 动态规划。设 dp[k][i][j] 表示只经过前 \(k\) 个节点作为中转时，\(i\) 到 \(j\) 的最短路。
状态转移方程：\(dp[k][i][j] = \min(dp[k-1][i][j], \ dp[k-1][i][k] + dp[k-1][k][j])\)
const int INF = 0x3f3f3f3f;
const int MAXN = 505;
int dp[MAXN][MAXN];
int n, m;
void floyd() {
// 初始化：dp[i][j] 表示 i 到 j 的距离
for (int k = 1; k <= n; k++) { // 中转点
for (int i = 1; i <= n; i++) { // 起点
for (int j = 1; j <= n; j++) { // 终点
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
}
}
}
}
// 使用前初始化
void init() {
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= n; i++) dp[i][i] = 0;
// 读入边并设置 dp[u][v] = w
}
时间复杂度： \(O(n^3)\)
空间优化： Floyd 天然可以原地更新，无需额外滚动数组。
11.4.5 最短路算法对比¶
| 算法 | 时间复杂度 | 负权边 | 适用场景 |
|---|---|---|---|
| Dijkstra 朴素 | \(O(n^2 + m)\) | 不支持 | 稠密图，无负权 |
| Dijkstra 堆优化 | \(O(m \log n)\) | 不支持 | 稀疏图，无负权（首选） |
| Bellman-Ford | \(O(nm)\) | 支持 | 有负权边，需判负环 |
| SPFA | \(O(km)\) 均摊 | 支持 | 有负权边的稀疏图 |
| Floyd | \(O(n^3)\) | 支持 | 全源最短路，\(n \leq 500\) |
11.5 最小生成树¶
最小生成树（MST） 是一棵包含图中所有 \(n\) 个节点、\(n - 1\) 条边的树，使得边权之和最小。前提是图连通。
11.5.1 Kruskal 算法¶
核心思想： 将所有边按边权从小到大排序，依次考虑每条边。如果这条边连接了两个不同的连通分量（用并查集判断），则加入答案。
贪心正确性： 假设当前最短的合法边 \(e\) 不在某棵 MST 中，将 \(e\) 加入 MST 会形成一个环，从环中删除比 \(e\) 更长的边，得到一棵更优的 MST，矛盾。
graph LR
subgraph "步骤1: 排序所有边"
E1["(A,B,1)"] --> E2["(B,C,2)"] --> E3["(A,C,3)"] --> E4["(C,D,4)"] --> E5["(B,D,5)"]
endstruct Edge {
int u, v, w;
bool operator<(const Edge& o) const {
return w < o.w;
}
};
vector<Edge> edges;
int parent[MAXN], rnk[MAXN];
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (rnk[x] < rnk[y]) swap(x, y);
parent[y] = x;
if (rnk[x] == rnk[y]) rnk[x]++;
return true;
}
int kruskal(int n) {
// 初始化并查集
for (int i = 1; i <= n; i++) parent[i] = i, rnk[i] = 0;
sort(edges.begin(), edges.end());
int mstWeight = 0, edgeCount = 0;
for (auto& e : edges) {
if (unite(e.u, e.v)) {
mstWeight += e.w;
edgeCount++;
if (edgeCount == n - 1) break;
}
}
// edgeCount < n-1 说明图不连通
return (edgeCount == n - 1) ? mstWeight : -1;
}
时间复杂度： \(O(m \log m)\)（排序主导）
11.5.2 Prim 算法¶
核心思想： 类似 Dijkstra，从任意节点出发，每次选择连接已选集合和未选集合的最短边，将其对应的未选节点加入集合。
朴素版 Prim¶
\(O(n^2 + m)\)，适用于稠密图。
const int INF = 0x3f3f3f3f;
int g[MAXN][MAXN];
int lowcost[MAXN]; // 到已选集合的最短距离
bool vis[MAXN];
int n;
int prim() {
memset(vis, false, sizeof(vis));
memset(lowcost, 0x3f, sizeof(lowcost));
lowcost[1] = 0;
int total = 0;
for (int i = 1; i <= n; i++) {
int u = -1;
for (int j = 1; j <= n; j++) {
if (!vis[j] && (u == -1 || lowcost[j] < lowcost[u])) {
u = j;
}
}
if (lowcost[u] == INF) return -1; // 不连通
vis[u] = true;
total += lowcost[u];
for (int v = 1; v <= n; v++) {
if (!vis[v] && g[u][v] < lowcost[v]) {
lowcost[v] = g[u][v];
}
}
}
return total;
}
堆优化版 Prim¶
\(O(m \log n)\)，适用于稀疏图。
const int INF = 0x3f3f3f3f;
struct Edge { int to, w; };
vector<Edge> adj[MAXN];
int lowcost[MAXN];
bool vis[MAXN];
int n;
int prim() {
memset(lowcost, 0x3f, sizeof(lowcost));
memset(vis, false, sizeof(vis));
lowcost[1] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
pq.push({0, 1});
int total = 0, cnt = 0;
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (vis[u]) continue;
vis[u] = true;
total += d;
cnt++;
for (auto& e : adj[u]) {
if (!vis[e.to] && e.w < lowcost[e.to]) {
lowcost[e.to] = e.w;
pq.push({e.w, e.to});
}
}
}
return (cnt == n) ? total : -1;
}
11.5.3 算法对比¶
| 算法 | 时间复杂度 | 适用场景 |
|---|---|---|
| Kruskal | \(O(m \log m)\) | 稀疏图首选，实现简单 |
| Prim 朴素 | \(O(n^2 + m)\) | 稠密图 |
| Prim 堆优化 | \(O(m \log n)\) | 稀疏图（与 Kruskal 相近） |
竞赛推荐：大多数情况下 Kruskal 更实用——只需排序 + 并查集，代码量少，不容易出错。
11.6 拓扑排序¶
拓扑排序 是对 DAG（有向无环图）的节点进行线性排序，使得对于每条有向边 \(\langle u, v \rangle\)，\(u\) 在排序中出现在 \(v\) 之前。
11.6.1 Kahn 算法（BFS 实现）¶
核心思想： 维护一个入度为 0 的节点队列。每次取出一个入度为 0 的节点，将它从图中"删除"（即将其所有邻居的入度减 1），新的入度为 0 的节点加入队列。
vector<int> adj[MAXN];
int indeg[MAXN];
int n, m;
vector<int> topoSort() {
queue<int> q;
for (int i = 1; i <= n; i++) {
if (indeg[i] == 0) q.push(i);
}
vector<int> order;
while (!q.empty()) {
int u = q.front();
q.pop();
order.push_back(u);
for (int v : adj[u]) {
if (--indeg[v] == 0) {
q.push(v);
}
}
}
// 如果排序结果不包含所有节点，说明有环
if ((int)order.size() != n) {
return {}; // 有环，拓扑排序不存在
}
return order;
}
时间复杂度： \(O(n + m)\)
11.6.2 判断 DAG¶
如果拓扑排序的结果包含所有 \(n\) 个节点，则图为 DAG；否则图中存在环。
11.6.3 入度变化图解¶
graph TD
subgraph "初始图"
A((A)) --> B((B))
A --> C((C))
B --> D((D))
C --> D
D --> E((E))
end
subgraph "步骤1: 选A(入度=0)"
B1((B: indeg 1->0))
C1((C: indeg 1->0))
D1((D: indeg 2))
E1((E: indeg 1))
end
subgraph "步骤2: 选B,C(入度=0)"
D2((D: indeg 2->0))
E2((E: indeg 1))
end
subgraph "步骤3: 选D(入度=0)"
E3((E: indeg 1->0))
end
subgraph "步骤4: 选E(入度=0)"
RESULT["排序: A -> B,C -> D -> E"]
end上图展示了一个拓扑排序过程：
| 步骤 | 选中节点 | 入度变化 |
|---|---|---|
| 1 | A（入度=0） | B: 1→0, C: 1→0 |
| 2 | B, C（入度=0） | D: 2→0 |
| 3 | D（入度=0） | E: 1→0 |
| 4 | E（入度=0） | 完成 |
最终排序：\(A \to B \to C \to D \to E\)（B 和 C 的相对顺序可交换）
11.6.4 应用¶
- 判断有向图是否有环：拓扑排序结果长度 \(< n\) 则有环。
- DAG 上的最短路/最长路：按拓扑序依次 DP，\(O(n + m)\)。
- 任务调度：确定有依赖关系的任务的执行顺序。
11.7 并查集¶
并查集（Disjoint Set Union, DSU / Union-Find） 是一种高效的集合合并与查询数据结构，广泛用于处理连通性问题。
11.7.1 基本操作¶
- find(x)：查找 \(x\) 所在集合的代表元素（根节点）。
- unite(x, y)：合并 \(x\) 和 \(y\) 所在的两个集合。
- same(x, y)：判断 \(x\) 和 \(y\) 是否在同一个集合。
11.7.2 基本实现¶
int parent[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) parent[i] = i;
}
int find(int x) {
if (parent[x] == x) return x;
return find(parent[x]); // 递归查找
}
void unite(int x, int y) {
parent[find(x)] = find(y);
}
bool same(int x, int y) {
return find(x) == find(y);
}
11.7.3 路径压缩¶
问题： 基本实现中，如果树退化成链，find 操作的复杂度退化为 \(O(n)\)。
路径压缩： 在 find 过程中，将路径上所有节点直接指向根节点，使树变得扁平。
11.7.4 按秩合并¶
秩（Rank） 是树的上界高度。合并时将矮树挂到高树上，避免树增高。
int parent[MAXN], rnk[MAXN];
void init(int n) {
for (int i = 1; i <= n; i++) {
parent[i] = i;
rnk[i] = 0;
}
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
void unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return;
if (rnk[x] < rnk[y]) swap(x, y);
parent[y] = x;
if (rnk[x] == rnk[y]) rnk[x]++;
}
11.7.5 树结构变化图解¶
graph TD
subgraph "初始: 每个节点独立"
A1((1)) ~~~ B1((2)) ~~~ C1((3)) ~~~ D1((4)) ~~~ E1((5))
end
subgraph "unite(1,2) 后"
A2((1)) --> B2((2))
C2((3)) ~~~ D2((4)) ~~~ E2((5))
end
subgraph "unite(3,4) 后"
A3((1)) --> B3((2))
C3((3)) --> D3((4))
E3((5))
end
subgraph "unite(1,3) 后（按秩合并）"
A4((1)) --> B4((2))
A4 --> C4((3))
C4 --> D4((4))
E4((5))
end
subgraph "路径压缩后 find(4)"
A5((1)) --> B5((2))
A5 --> C5((3))
A5 --> D5((4))
E5((5))
end11.7.6 复杂度分析¶
| 操作 | 仅路径压缩 | 仅按秩合并 | 路径压缩 + 按秩合并 |
|---|---|---|---|
| 单次均摊 | \(O(\log n)\) | \(O(\log n)\) | \(O(\alpha(n))\) |
其中 \(\alpha(n)\) 是反阿克曼函数，增长极其缓慢，对所有实际输入 \(\alpha(n) \leq 5\)，可以认为是常数时间。
11.7.7 完整代码模板¶
struct DSU {
vector<int> parent, rnk;
int components; // 连通分量个数
DSU(int n) : parent(n + 1), rnk(n + 1, 0), components(n) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (rnk[x] < rnk[y]) swap(x, y);
parent[y] = x;
if (rnk[x] == rnk[y]) rnk[x]++;
components--;
return true;
}
bool same(int x, int y) {
return find(x) == find(y);
}
};
11.7.8 带权并查集（拓展）¶
在某些问题中，节点之间存在某种关系（如距离、权值），可以为每个节点维护一个额外的 val 数组表示与父节点的关系。
int parent[MAXN], val[MAXN]; // val[x] 表示 x 到 parent[x] 的权值差
int find(int x) {
if (parent[x] == x) return x;
int root = find(parent[x]);
val[x] += val[parent[x]]; // 路径压缩时更新权值
return parent[x] = root;
}
void unite(int x, int y, int w) {
// 表示 y = x + w 的关系
int fx = find(x), fy = find(y);
if (fx != fy) {
parent[fy] = fx;
val[fy] = val[x] + w - val[y];
}
}
练习题¶
ACM Day6 图论（11题）¶
| 编号 | 题号 | 题目名称 | 知识点 | 难度 |
|---|---|---|---|---|
| 1 | 2041D | Cross Coloring | 图的着色 / 连通性 | 1500 |
| 2 | 2023B | Increase/Decrease/Copy | 图论建模 / 贪心 | 1400 |
| 3 | 1915G | Bicycles | 最短路（Dijkstra） | 1700 |
| 4 | 2014E | Treasure Hunt | BFS / 图上搜索 | 1600 |
| 5 | 1975D | Paint the Tree | 树的直径 / BFS / DFS | 1800 |
| 6 | 2060E | Graph Compression | 并查集 / 图论 | 1700 |
| 7 | 2027C | Add Zeros | 图论建模 / BFS | 1900 |
| 8 | abc384_e | Takahashi's Angry 2 | BFS / 优先队列 | 黄 |
| 9 | arc185_d | Palindrome Factory | 图论 / 构造 | 蓝 |
| 10 | P1144 | 最短路计数 | Dijkstra + DP | 普及/提高 |
| 11 | P9754 | [CSP-S 2023] 消消乐 | 图论建模 / 拓扑排序 | 提高+/省选 |
LeetCode 寒假补充¶
| 编号 | 题号 | 题目名称 | 知识点 | 难度 |
|---|---|---|---|---|
| 1 | 200 | 岛屿数量 | DFS / BFS / 连通分量 | Medium |
| 2 | 695 | 岛屿的最大面积 | DFS / 连通分量 | Medium |
| 3 | 102 | 二叉树的层序遍历 | BFS | Medium |
本章小结： 图是算法竞赛的核心数据结构。掌握图的存储方式（邻接表为首选）和两种遍历方式（DFS/BFS）是基础中的基础。最短路算法要根据图的特点（是否有负权、稀疏还是稠密、单源还是多源）选择合适的算法。最小生成树推荐 Kruskal + 并查集。拓扑排序是 DAG 上的基础操作。并查集要熟练掌握路径压缩和按秩合并，它是处理连通性问题的利器。