Ginkgo
True love prevails.
写这篇的初衷:图论算法模板多、变种多,死记硬背很容易混淆。这篇试着从”什么时候用”和”为什么有效”两个角度重新整理,帮你建立直觉。
图论的本质:把实际问题抽象成点和边的关系 ,然后用搜索或贪心/动态规划来解决。
一、DFS 与 BFS:两种搜索策略 DFS 深度优先搜索 —— “一条路走到黑” 核心直觉 :像一个很执着的人,选一条路一直走,走不通了再 backtrack 回来换下一条。
适用场景 :
枚举所有可能情况(全排列、组合)
连通性问题(判断两点是否可达)
树的遍历
需要”回溯”的问题(八皇后、数独)
空间复杂度 : ,h 是递归深度(栈空间)
关键技巧 :
恢复现场 :回溯时要撤销之前的修改
剪枝 :提前判断某条路走不通,直接返回
模板:全排列问题 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 const int N = 10 ;int n;int path[N]; bool st[N]; void dfs (int u) { if (u == n) { for (int i = 0 ; i < n; i++) cout << path[i] << ' ' ; cout << '\n' ; return ; } for (int i = 1 ; i <= n; i++) { if (!st[i]) { st[i] = true ; path[u] = i; dfs (u + 1 ); st[i] = false ; } } }
为什么需要恢复现场 :因为 st[i] 表示”这个数在当前路径中是否被使用”,回溯后要让它能被其他分支使用。
经典例题:八皇后问题 问题 :在 n×n 棋盘上放 n 个皇后,使它们互不攻击(不在同一行、列、对角线)。
思路 1:按行枚举 (推荐,更快)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 const int N = 20 ; int n;char g[N][N];bool col[N], dg[N], udg[N]; void dfs (int u) { if (u == n) { for (int i = 0 ; i < n; i++) puts (g[i]); cout << '\n' ; return ; } for (int i = 0 ; i < n; i++) { if (!col[i] && !dg[u + i] && !udg[n - u + i]) { g[u][i] = 'Q' ; col[i] = dg[u + i] = udg[n - u + i] = true ; dfs (u + 1 ); col[i] = dg[u + i] = udg[n - u + i] = false ; g[u][i] = '.' ; } } }
思路 2:按格子枚举 (每个格子放或不放)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 void dfs (int x, int y, int s) { if (y == n) y = 0 , x++; if (x == n) { if (s == n) { for (int i = 0 ; i < n; i++) puts (g[i]); cout << '\n' ; } return ; } dfs (x, y + 1 , s); if (!row[x] && !col[y] && !dg[x + y] && !udg[x - y + n]) { g[x][y] = 'Q' ; row[x] = col[y] = dg[x + y] = udg[x - y + n] = true ; dfs (x, y + 1 , s + 1 ); row[x] = col[y] = dg[x + y] = udg[x - y + n] = false ; g[x][y] = '.' ; } }
为什么思路 1 更快 :思路 1 隐含了”每行必须放一个”的先验知识,搜索空间更小。思路 2 需要枚举每个格子放或不放,复杂度更高。
BFS 宽度优先搜索 —— “广撒网” 核心直觉 :像波纹一样一圈圈向外扩散,先访问离起点近的点,再访问远的点。
适用场景 :
最短路问题 (边权为 1 时,BFS 第一次到达的点就是最短距离)
层次遍历(树的层序遍历)
状态空间搜索(如迷宫、拼图)
空间复杂度 : ,需要存一层的所有节点
关键性质 :BFS 具有最短性 ——第一次扩展到某个点时,走的步数一定是最少的。
模板:迷宫最短路 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 const int N = 110 ;int n, m;int g[N][N]; int d[N][N]; int bfs () { queue<pair<int , int >> q; q.push ({0 , 0 }); memset (d, -1 , sizeof d); d[0 ][0 ] = 0 ; int dx[4 ] = {-1 , 0 , 1 , 0 }, dy[4 ] = {0 , 1 , 0 , -1 }; while (!q.empty ()) { auto [x, y] = q.front (); q.pop (); for (int i = 0 ; i < 4 ; i++) { int nx = x + dx[i], ny = y + dy[i]; if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny] == 0 && d[nx][ny] == -1 ) { d[nx][ny] = d[x][y] + 1 ; q.push ({nx, ny}); } } } return d[n - 1 ][m - 1 ]; }
如何记录路径? 额外开一个数组记录每个点是从哪个点扩展过来的:
1 2 3 4 5 6 7 8 9 10 11 12 pair<int , int > prev[N][N]; prev[nx][ny] = {x, y}; int x = n - 1 , y = m - 1 ;while (x || y) { cout << x << ' ' << y << '\n' ; auto [px, py] = prev[x][y]; x = px, y = py; }
BFS 与 DP 的关系 最短路问题本质上是一种 DP :
状态:d[i] 表示从起点到 i 的最短距离
转移:d[v] = min(d[v], d[u] + 1)
无环:BFS 保证每个点只被更新一次
区别 :DP 通常用于 DAG(有向无环图),而 BFS 可以处理任意无权图。
二、树与图的存储 核心概念
树 :无环连通图,n 个点 n-1 条边
图 :点 + 边的集合,分有向图和无向图
无向图 :可以看成每条边连了两次的有向图
存储方式对比 邻接矩阵
优点 :判断两点是否有边是
缺点 :空间 ,适合稠密图
适用 :点数较少(n ≤ 1000)的稠密图
邻接表(vector 实现) 1 2 3 4 5 6 7 8 9 10 11 12 struct Edge { int to, w; }; vector<vector<Edge>> gt (n + 1 ); gt[u].emplace_back (v, w); for (auto & e : gt[u]) { int v = e.to, w = e.w; }
优点 :空间 ,适合稀疏图
缺点 :判断两点是否有边需要遍历
数组模拟邻接表(竞赛常用) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 const int N = 100010 , M = N * 2 ; int h[N], e[M], ne[M], w[M], idx;void init () { memset (h, -1 , sizeof h); idx = 0 ; } void add (int u, int v, int c) { e[idx] = v, w[idx] = c, ne[idx] = h[u], h[u] = idx++; } for (int i = h[u]; i != -1 ; i = ne[i]) { int v = e[i], c = w[i]; }
为什么用数组模拟 :
避免动态内存分配,速度更快
内存连续,缓存友好
不会内存泄漏
链式前向星 本质上和数组模拟邻接表是一回事,只是用结构体包装了一下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 struct Edge { int to, w, next; } edge[M]; int head[N], idx;void add (int u, int v, int w) { edge[idx] = {v, w, head[u]}; head[u] = idx++; } for (int i = head[u]; i != -1 ; i = edge[i].next) { int v = edge[i].to, w = edge[i].w; }
理解技巧 :把 head[u] 看成链表头,next 指针把同一起点的边串起来。
树的遍历 BFS :层序遍历(从上到下一层一层访问)
DFS :
前序遍历:根→左→右
中序遍历:左→根→右
后序遍历:左→右→根
三、树与图的 DFS 模板 1 2 3 4 5 6 7 8 9 bool st[N]; void dfs (int u) { st[u] = true ; for (int i = h[u]; i != -1 ; i = ne[i]) { int j = e[i]; if (!st[j]) dfs (j); } }
经典应用:树的重心 问题 :删掉哪个点后,最大连通块最小?
思路 :DFS 过程中计算每个子树的大小,同时更新答案。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int n, ans = N;bool st[N];int dfs (int u) { st[u] = true ; int sum = 1 , res = 0 ; for (int i = h[u]; i != -1 ; i = ne[i]) { int j = e[i]; if (!st[j]) { int s = dfs (j); res = max (res, s); sum += s; } } res = max (res, n - sum); ans = min (ans, res); return sum; }
关键点 :删掉 u 后,连通块最多有三部分:左子树、右子树、整棵树减去以 u 为根的子树。
四、树与图的 BFS 模板:求点的层次 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int d[N]; int bfs () { queue<int > q; q.push (1 ); memset (d, -1 , sizeof d); d[1 ] = 0 ; while (!q.empty ()) { int t = q.front (); q.pop (); for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i]; if (d[j] == -1 ) { d[j] = d[t] + 1 ; q.push (j); } } } return d[n]; }
适用场景 :所有边权都是 1 的最短路问题
五、拓扑排序 核心概念 拓扑序列 :对于有向图的每条边 (u, v),u 在序列中都出现在 v 前面。
存在条件 :有向无环图(DAG) 一定存在拓扑序列
应用 :
任务调度(某些任务必须在其他任务之前完成)
判环(如果不存在拓扑序列,说明有环)
算法思路
将所有入度为 0 的点入队
每次取出队头 t,把 t 的所有出边终点的入度 -1
如果某个点入度变为 0,入队
如果最终所有点都入队过,存在拓扑序列;否则有环
模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int d[N]; int q[N], hh = 0 , tt = -1 ;int res[N], cnt = 0 ; bool topsort () { for (int i = 1 ; i <= n; i++) if (!d[i]) q[++tt] = i; while (hh <= tt) { int t = q[hh++]; res[cnt++] = t; for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i]; d[j]--; if (!d[j]) q[++tt] = j; } } return cnt == n; }
注意 :拓扑序列不唯一 。OJ 中对于多解的情况会用 Special Judge (SPJ) 判断。
六、最短路算法全家桶 问题分类
类型
描述
算法
单源最短路
从一个点到其他所有点
Dijkstra, Bellman-Ford, SPFA
多源汇最短路
任意两点之间的最短路
Floyd
边权情况 :
所有边权为正:Dijkstra
存在负权边:Bellman-Ford / SPFA
存在负环:最短路可能不存在
Dijkstra 算法 核心思想 :贪心。每次选当前距离起点最近的点,用它更新其他点。
限制 :不能有负权边 (贪心不再成立)
朴素版 Dijkstra 适用 :稠密图( ),用邻接矩阵
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 const int N = 510 , INF = 0x3f3f3f3f ;int g[N][N], dist[N];bool st[N]; int dijkstra (int n) { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; for (int i = 0 ; i < n; i++) { int t = -1 ; for (int j = 1 ; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; st[t] = true ; for (int j = 1 ; j <= n; j++) dist[j] = min (dist[j], dist[t] + g[t][j]); } return dist[n] == INF ? -1 : dist[n]; }
为什么正确 :每次迭代确定一个点的最短路,n 次迭代后所有点都确定。
堆优化 Dijkstra 适用 :稀疏图( ),用邻接表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 const int N = 100010 , M = N * 2 , INF = 0x3f3f3f3f ;int h[N], e[M], w[M], ne[M], idx;int dist[N];bool st[N];typedef pair<int , int > PII;int dijkstra (int n) { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push ({0 , 1 }); while (!heap.empty ()) { auto [d, u] = heap.top (); heap.pop (); if (st[u]) continue ; st[u] = true ; for (int i = h[u]; i != -1 ; i = ne[i]) { int v = e[i], c = w[i]; if (dist[v] > d + c) { dist[v] = d + c; heap.push ({dist[v], v}); } } } return dist[n] == INF ? -1 : dist[n]; }
为什么需要 st 数组 :同一个点可能被多次加入堆(每次距离更新都加一次),但只有第一次弹出时是最优的。
Dijkstra vs Bellman-Ford
对比项
Dijkstra
Bellman-Ford
时间复杂度
或
负权边
❌ 不支持
✅ 支持
稠密图性能
边数限制
无
可限制经过边数
结论 :没有负权边时,Dijkstra 通常比 Bellman-Ford 快很多。
Bellman-Ford 算法 核心思想 :松弛操作。对所有边进行 n-1 轮松弛,每轮尝试更新所有点。
适用场景 :
存在负权边
限制经过的边数不超过 k (这是 SPFA 做不到的)
原理 :最短路最多经过 n-1 条边(否则有环)。n-1 轮松弛后一定收敛。
模板(限制边数版) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 const int N = 510 , M = 10010 , INF = 0x3f3f3f3f ;int n, m, k;int dist[N], backup[N];struct Edge { int u, v, w; } edges[M]; int bellman_ford () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; for (int i = 0 ; i < k; i++) { memcpy (backup, dist, sizeof dist); for (int j = 0 ; j < m; j++) { auto [u, v, w] = edges[j]; dist[v] = min (dist[v], backup[u] + w); } } return dist[n] > INF / 2 ? -1 : dist[n]; }
为什么要备份 :防止一轮中多次更新(串联)。比如 1→2→3,如果不用 backup,可能一轮中 1 更新了 2,2 又更新了 3,相当于走了两条边。
SPFA 算法 核心思想 :Bellman-Ford 的优化。只有距离被更新的点,才需要去更新它的邻居。
实现 :用队列维护需要更新的点
时间复杂度 :平均 ,最坏
限制 :不能有负环
模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 const int N = 100010 , M = N * 2 , INF = 0x3f3f3f3f ;int h[N], e[M], w[M], ne[M], idx;int dist[N];bool st[N]; int spfa () { memset (dist, 0x3f , sizeof dist); dist[1 ] = 0 ; queue<int > q; q.push (1 ); st[1 ] = true ; while (!q.empty ()) { int t = q.front (); q.pop (); st[t] = false ; for (int i = h[t]; i != -1 ; i = ne[i]) { int j = e[i], c = w[i]; if (dist[j] > dist[t] + c) { dist[j] = dist[t] + c; if (!st[j]) { q.push (j); st[j] = true ; } } } } return dist[n] == INF ? -1 : dist[n]; }
SPFA 被”卡”是什么意思? 可以构造特殊数据让 SPFA 退化成 ,这时候就很慢。一般遇到这种情况换堆优化 Dijkstra(如果没有负权边)。
判负环 思路 :记录最短路经过的边数,如果某条路径边数 ≥ n,说明有负环。
1 2 3 4 5 6 7 8 int cnt[N]; if (dist[j] > dist[t] + c) { dist[j] = dist[t] + c; cnt[j] = cnt[t] + 1 ; if (cnt[j] >= n) return true ; }
注意 :如果要判断整个图 是否存在负环(不一定是从 1 出发),需要一开始把所有点都放入队列。
Floyd 算法 核心思想 :动态规划。三重循环,暴力美学。
适用 :多源最短路(求任意两点间的最短距离)
时间复杂度 :
限制 :不能有负环(但可以处理负权边)
模板 1 2 3 4 5 6 7 8 9 10 const int N = 210 , INF = 0x3f3f3f3f ;int n, m, Q;int d[N][N]; void floyd () { for (int k = 1 ; k <= n; k++) for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) d[i][j] = min (d[i][j], d[i][k] + d[k][j]); }
DP 解释 :
状态:d[k][i][j] 表示从 i 到 j,只经过 1~k 这些中间点的最短距离
转移:d[k][i][j] = min(d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j])
优化:第一维可以省略
七、最小生成树 问题描述 场景 :n 个城市,m 条可选道路,选 n-1 条路使所有城市连通且总代价最小。
前提 :无向图,边权可正可负
Prim 算法 核心思想 :类似 Dijkstra。维护一个”已选点集合”,每次选距离集合最近的点加入。
朴素版 Prim 适用 :稠密图
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 const int N = 510 , INF = 0x3f3f3f3f ;int g[N][N], dist[N];bool st[N];int prim (int n) { memset (dist, 0x3f , sizeof dist); int res = 0 ; for (int i = 0 ; i < n; i++) { int t = -1 ; for (int j = 1 ; j <= n; j++) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; if (i && dist[t] == INF) return INF; if (i) res += dist[t]; for (int j = 1 ; j <= n; j++) dist[j] = min (dist[j], g[t][j]); st[t] = true ; } return res; }
和 Dijkstra 的区别 :dist[j] 的含义不同。Dijkstra 是”到起点的距离”,Prim 是”到已选集合的距离”。
堆优化 Prim 适用 :稀疏图(但一般不常用,Kruskal 更简单)
Kruskal 算法 核心思想 :贪心。把所有边从小到大排序,依次选边,如果边的两端不连通就加入。
时间复杂度 : (排序的复杂度)
适用 :稀疏图
模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 const int N = 100010 , M = 200010 ;int n, m;int p[N]; struct Edge { int a, b, w; bool operator <(const Edge& W) const { return w < W.w; } } edges[M]; int find (int x) { if (p[x] != x) p[x] = find (p[x]); return p[x]; } int kruskal () { sort (edges, edges + m); for (int i = 1 ; i <= n; i++) p[i] = i; int res = 0 , cnt = 0 ; for (int i = 0 ; i < m; i++) { auto [a, b, w] = edges[i]; a = find (a), b = find (b); if (a != b) { p[a] = b; res += w; cnt++; } } return cnt < n - 1 ? INF : res; }
Prim vs Kruskal
对比项
Prim
Kruskal
时间复杂度
或
稠密图
✅ 更优
❌ 排序开销大
稀疏图
❌
✅ 更优
实现难度
中等
简单(需要并查集)
建议 :稀疏图用 Kruskal,稠密图用 Prim。
八、二分图 核心概念 二分图 :可以把所有点分成两组,所有边都只连接不同组的点。
判定定理 :一个图是二分图 当且仅当 图中不含奇数环
染色法判定 思路 :用 DFS 给每个点染色(1 或 2),相邻点颜色必须不同。如果出现冲突,不是二分图。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 const int N = 100010 , M = 200010 ;int h[N], e[M], ne[M], idx;int color[N]; bool dfs (int u, int c) { color[u] = c; for (int i = h[u]; i != -1 ; i = ne[i]) { int j = e[i]; if (!color[j]) { if (!dfs (j, 3 - c)) return false ; } else if (color[j] == c) return false ; } return true ; } bool is_bipartite = true ;for (int i = 1 ; i <= n; i++) if (!color[i] && !dfs (i, 1 )) { is_bipartite = false ; break ; }
为什么是 3-c :c 是 1 或 2,3-c 就是相反的颜色。
匈牙利算法 问题 :求二分图的最大匹配(最多能配多少对)
时间复杂度 : ,但实际运行远小于这个上界
核心思想 :贪心 + 回溯。”待字闺中,据为己有;名花有主,求他放手。”
模板 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 const int N = 510 , M = 100010 ;int h[N], e[M], ne[M], idx;int match[N]; bool st[N]; bool find (int x) { for (int i = h[x]; i != -1 ; i = ne[i]) { int j = e[i]; if (!st[j]) { st[j] = true ; if (!match[j] || find (match[j])) { match[j] = x; return true ; } } } return false ; } int res = 0 ;for (int i = 1 ; i <= n1; i++) { memset (st, false , sizeof st); if (find (i)) res++; }
st[] 的作用 :防止一轮 DFS 中重复访问同一个点。每轮开始前要清空。
经典例题:棋盘覆盖 问题 :N×N 棋盘,某些格子禁止放置。求最多能放多少个 1×2 的骨牌。
建模 :
每个格子是一个点
相邻格子连边
问题转化为:选最多的不相交边 → 最大匹配
二分图构造 :按 (i + j) % 2 分组,相邻格子一定在不同组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 const int N = 110 ;bool ban[N][N];int h[N * N], e[N * N * 4 ], ne[N * N], idx;int match[N * N];bool st[N * N];int get (int x, int y) { return (x - 1 ) * N + y; } for (int i = 1 ; i <= n; i++) { for (int j = 1 ; j <= n; j++) { if (ban[i][j]) continue ; if ((i + j) % 2 == 0 ) { int dx[4 ] = {0 , 1 , 0 , -1 }, dy[4 ] = {1 , 0 , -1 , 0 }; for (int k = 0 ; k < 4 ; k++) { int ni = i + dx[k], nj = j + dy[k]; if (ni >= 1 && ni <= n && nj >= 1 && nj <= n && !ban[ni][nj]) add (get (i, j), get (ni, nj)); } } } } int res = 0 ;for (int i = 1 ; i <= n; i++) for (int j = 1 ; j <= n; j++) if ((i + j) % 2 == 0 && !ban[i][j]) { memset (st, false , sizeof st); if (find (get (i, j))) res++; }
小结:图论算法选择指南
问题类型
推荐算法
时间复杂度
枚举所有方案
DFS + 回溯
指数级
无权图最短路
BFS
有向无环图排序
拓扑排序
单源最短路(正权)
Dijkstra(堆优化)
单源最短路(负权)
SPFA / Bellman-Ford
平均
限制边数的最短路
Bellman-Ford
多源最短路
Floyd
最小生成树(稠密)
Prim
最小生成树(稀疏)
Kruskal
二分图判定
染色法
二分图最大匹配
匈牙利算法
最后提醒 :图论算法的核心是建模 ——把实际问题抽象成点和边的关系。模板好背,建模难练,多做题多思考才是王道。