搞图论算法题最怕的不是思路难而是每次写代码都要重新从零敲一遍建图、DFS、最短路。明明都是些固定套路却因为某个细节写错浪费几个小时这种亏我吃过太多次。后来我把图论里常用到的算法模板整理成一套自己的代码库刷题时直接调省下的时间全用来想题目的核心逻辑。今天就把这套模板的核心思路和完整写法分享出来适合准备算法竞赛、刷LeetCode图论题、或者面试前突击图论的朋友参考。这套内容覆盖了图的存储、遍历、拓扑排序、最短路、最小生成树、连通性、二分图匹配和网络流这些常见高频考点。我不光会贴模板还会把每个模板背后“为什么要这么写”“哪些地方容易踩坑”讲清楚。你不需要全部背下来但建议把每段代码跑一遍改成自己的风格最后形成属于你自己的图论模板库。1. 图论模板的整体设计与思路拆解1.1 为什么竞赛与刷题需要“模板化”很多人觉得写算法题死记模板没出息但关键在于“模板化”和“背题”是两回事。图论问题千变万化但底层的基础操作极其固定。拿最短路来说无论题目如何包装最后解法的核心还是那几种算法。如果你能把这些基础算法写得又快又准就能把宝贵的比赛时间花在对题目的分析上而不是浪费在调试一眼就能看出的边界错误上。另外模板化的过程也是一个深度理解算法的过程。当你把Dijkstra、Tarjan这些算法亲手写成固定格式时你一定需要理解它的每一步在干什么。写完模板之后再遇到问题你的脑子里会直接浮现出这套代码结构做题速度会有质的提升。1.2 图论知识体系与模板分类图论的基础知识可以分为几个大的模块。第一个是存储结构包括邻接矩阵、邻接表、链式前向星。第二个是遍历包括深度优先搜索和广度优先搜索它们是很多图论算法的基础。第三个是路径问题包括单源最短路和全源最短路。第四个是生成树问题包括最小生成树和次小生成树。第五个是连通性问题包括并查集、强连通分量、割点、桥。第六个是匹配问题主要是二分图最大匹配。第七个是进阶的网络流问题最大流、费用流。我在整理模板时会按这个模块去分类。每个模块里的算法都有一份经过反复测试的代码需要时直接复制使用。下面我按照这个顺序把每个模板的关键代码和设计思路逐步拆给大家。2. 图的存储与遍历基础模板2.1 三种存图方式对比与选择存图是图论问题的第一步。这里我平时只考虑三种方式邻接矩阵、vector邻接表、链式前向星。邻接矩阵适合点少边多的稠密图点的数量在1000以内时很好用因为g[u][v] w可以直接判断两个点是否相连代码最简单。但一旦点数到10000以上矩阵的存储空间就是n^2级别会直接爆内存。vector邻接表是日常刷题最推荐的方式。用vectorpairint, int g[N]存带权图g[u].push_back({v, w})既能表示边的指向又能存边权写起来直观遍历也方便。不过vector在动态扩容时会有一定的性能损耗在一些对时间极度敏感的大型比赛中可能会比链式前向星慢一点。链式前向星是竞赛选手最常用的方式。它本质上是用数组模拟链表每个节点代表一条边通过head[u]找到的边索引再通过next指针遍历所有邻边。优点是可以静态分配内存遍历速度极快而且能够处理重边。缺点是可读性差一点写起来容易出错。我给出的模板是这样的const int MAXN 100005; // 点数 const int MAXM 200005; // 边数 struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].w w; edges[cnt].next head[u]; head[u] cnt; } // 遍历u的所有邻边 for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; int w edges[e].w; }初始化时要把head数组全部置为-1。我看到很多新手会忘记这一步导致遍历时死循环或者数组越界。用memset(head, -1, sizeof(head))即可。至于选择策略如果你在竞赛中追求极致性能就用链式前向星如果是日常刷题或面试vector邻接表完全够用。2.2 DFS和BFS的模板写法深度优先搜索DFS和广度优先搜索BFS是图论算法里出现频率最高的遍历方式。DFS常用来做连通性检测、环检测、拓扑排序、Tarjan那类算法的基础BFS则常用于无权图最短路、层次遍历等场景。DFS递归模板很简单vectorint g[MAXN]; bool vis[MAXN]; void dfs(int u) { vis[u] true; // 处理当前节点的业务逻辑 for (int v : g[u]) { if (!vis[v]) { dfs(v); } } }这个模板需要注意的点是递归深度。当图是一条长度为10万的链时递归调用会导致栈溢出。这种时候需要改成显式栈stackint st; st.push(start); vis[start] true; while (!st.empty()) { int u st.top(); st.pop(); // 处理节点 for (int v : g[u]) { if (!vis[v]) { vis[v] true; st.push(v); } } }BFS模板同样基础却极其重要queueint q; vectorint dist(N, -1); dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }BFS最关键的设计是用dist[v] -1同时充当“是否访问过”和“距离”两个角色避免单独开一个visited数组。这也是图论模板里常见的“状态压缩”思路。对于无权图BFS天然能求单源最短路复杂度是O(VE)比Dijkstra还快。2.3 拓扑排序从队列到优先队列拓扑排序用于有向无环图DAG解决任务依赖、课程安排这类问题。核心思想是每次取一个入度为0的点删除它的所有出边更新其他点入度重复操作。如果最后取出的点数不等于总点数说明图中有环。普通拓扑排序模板Kahn算法vectorint g[MAXN]; int indeg[MAXN]; vectorint topo; // 存放拓扑序列 bool topoSort(int n) { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) { q.push(v); } } } return (int)topo.size() n; }注意这里用--indeg[v] 0来判断比先减再判断更简洁。如果需要输出字典序最小的拓扑排序就把队列换成优先队列每次取出编号最小的入度为0的节点priority_queueint, vectorint, greaterint pq;这个变换在很多LeetCode题里都出现过比如“课程表II”要求返回字典序结果。模板里的优先队列用greaterint实现小根堆可以保证每次弹出的节点编号最小。这里还有个隐藏难点优先队列模板不能直接用于求“全局字典序最小”因为它只保证局部字典序最小但这个在拓扑排序场景下恰好等价于最终字典序最小因为每一步能取的节点中取最小的那个不会影响后续节点的可选性。3. 最短路算法模板3.1 Dijkstra堆优化模板与正确性Dijkstra算法处理的是非负权单源最短路问题。最经典的写法是用优先队列堆优化每次取出当前距离最小的点进行松弛。这里有一个非常容易出错的地方优先队列里可能会存同一个点的多个历史状态所以必须用vis数组去重避免同一个点被重复处理。堆优化的Dijkstra模板const int INF 0x3f3f3f3f; struct Node { int v, w; bool operator(const Node other) const { return w other.w; // 小根堆 } }; vectorNode g[MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { int u pq.top().v; pq.pop(); if (vis[u]) continue; vis[u] true; for (auto e : g[u]) { int v e.v; int w e.w; if (!vis[v] dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } }代码中Node结构体里重载operator时取w other.w这是C优先队列默认大根堆的反向写法千万不要搞反。INF用0x3f3f3f3f而不是INT_MAX是因为0x3f3f3f3f加上一个权值不会溢出而且可以用memset按字节填充得到的就是0x3f3f3f3f非常方便。Dijkstra的正确性基于贪心思想已确定最短路的点集合中每次选距离最远的未确定点加入之后不会再被其他点更新。这个结论只有在所有边权非负时才成立。一旦出现负边堆优化Dijkstra就会失效必须改用SPFA或Bellman-Ford。3.2 SPFA与Bellman-Ford负环判断SPFA算法是Bellman-Ford的队列优化在稀疏图上表现很好最坏复杂度可能退化成O(VE)所以一些出题人会故意构造数据卡SPFA。虽然如此SPFA依然是处理负权边的最常用模板并且能判断负环。SPFA普通模板vectorpairint, int g[MAXN]; int dist[MAXN]; int cnt[MAXN]; // 记录每个点入队次数 bool inq[MAXN]; bool spfa(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inq, false, sizeof(inq)); dist[s] 0; queueint q; q.push(s); inq[s] true; cnt[s] 1; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { q.push(v); inq[v] true; if (cnt[v] n) { return false; // 存在负环 } } } } } return true; }这里的cnt[v]表示点v入队的总次数如果某个点入队次数超过n点数说明图中存在负环。负环会让最短路不断变小所以必须判断并返回。SPFA还有一个常见优化SLFSmall Label First即如果当前节点距离小于队首距离则插到队首。在稀疏图上效果不错但也不是万能。我更推荐在非负权图里直接用Dijkstra只在有负权时才用SPFA。Bellman-Ford模板可以不写队列优化直接用n-1轮松弛for (int i 1; i n; i) { bool updated false; for (int e 1; e m; e) { int u edges[e].u, v edges[e].v, w edges[e].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; updated true; } } if (!updated) break; }第n轮如果还能松弛说明有负环。对于新手我建议直接背SPFA模板因为它在大多数情况下更快同时保留了Bellman-Ford的思路。3.3 Floyd全源最短路实现细节Floyd算法用于求任意两点间的最短路复杂度O(n^3)适合点数很小一般n300的场景。它的核心是动态规划思想int dis[MAXN][MAXN]; void floyd(int n) { for (int k 1; k n; k) { for (int i 1; i n; i) { if (dis[i][k] INF) continue; // 优化 for (int j 1; j n; j) { if (dis[i][j] dis[i][k] dis[k][j]) { dis[i][j] dis[i][k] dis[k][j]; } } } } }非常重要的一个细节是最外层循环必须是k也就是中间点。因为dis[i][j]的更新依赖于dis[i][k]和dis[k][j]只有先枚举中间点才能保证每个中间点的状态都已经被计算过。这个顺序错了结果就会错得离谱却很难发现。初始化时dis[i][i] 0其他不存在的边设为INF注意INF不能太大不然相加会溢出通常设置成0x3f3f3f3f约10^9就够了。Floyd还可以顺便求最小环做法是每次枚举中间点k之前检查dis[i][j] g[i][k] g[k][j]是否构成环这个进阶用法在遇到“求有向图最小环”的题目时很有用。4. 最小生成树与连通性模板4.1 Kruskal与Prim模板最小生成树问题最常用的是Kruskal算法因为它实现简单、复杂度优秀。核心思想是把所有边按权重从小到大排序然后依次加入边如果加入后不形成环就保留这条边。判断是否成环用并查集。Kruskal模板struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } } edges[MAXM]; int parent[MAXN]; int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } int kruskal(int n, int m) { sort(edges 1, edges m 1); for (int i 1; i n; i) parent[i] i; int ans 0, cnt 0; for (int i 1; i m; i) { int ru find(edges[i].u); int rv find(edges[i].v); if (ru ! rv) { parent[ru] rv; ans edges[i].w; if (cnt n - 1) break; } } return cnt n - 1 ? ans : -1; // 返回-1表示图不连通 }注意find函数里用了路径压缩。parent[ru] rv也能用按秩合并优化但在路径压缩已经很快的前提下按秩合并不是必须的不过在极端数据下能进一步稳定复杂度。Prim算法则适合稠密图尤其是邻接矩阵存图时写起来非常简洁。它的思路是从一个点开始不断找离已选点集合最近的未选点加入。普通实现复杂度O(n^2)堆优化后是O((VE)logV)。竞赛中如果图是稠密的直接使用堆优化Prim。堆优化Prim模板priority_queueNode, vectorNode, greaterNode pq; bool vis[MAXN]; int dist[MAXN]; // 到当前生成树集合的最短距离 int prim(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; int ans 0, cnt 0; pq.push({s, 0}); while (!pq.empty()) { auto [u, du] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; ans du; cnt; for (auto e : g[u]) { int v e.v, w e.w; if (!vis[v] w dist[v]) { dist[v] w; pq.push({v, dist[v]}); } } } if (cnt ! n) return -1; return ans; }Prim算法容易犯的错误是忘记判断vis导致一个点被重复加入。模板中用if (vis[u]) continue剔除了堆里的过期节点这个和Dijkstra非常相似。4.2 并查集优化技巧并查集虽然不算单独的一类图论问题但它几乎出现在所有连通性相关的模板中。除了路径压缩还有一个重要的优化是“按秩合并”即让深度较小的树合并到深度较大的树上。路径压缩之后单独使用秩合并的意义会变小但两者结合可以让并查集的操作接近O(alpha(n))alpha是反阿克曼函数可以认为是一个常数。模板如下int parent[MAXN]; int rnk[MAXN]; void init(int n) { for (int i 1; i n; i) { parent[i] i; rnk[i] 1; } } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return 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; rnk[x] rnk[y]; }rnk存的是集合大小合并时让小集合挂到大集合下面。这样能够避免退化链的出现即使不路径压缩也能保持log级别的树高。日常写题时只用路径压缩通常也足够但把秩合并背下来可以应对刷题网站上的特殊构造数据。4.3 Tarjan求强连通分量与缩点强连通分量SCC是很多有向图问题的必经之路。Tarjan算法通过DFS的时间戳和栈来划分强连通分量。对于基于强连通分量的题目一般还要做“缩点”操作将所有SCC压缩成DAG上的一个点然后在DAG上做DP或拓扑排序。Tarjan模板vectorint g[MAXN]; int dfn[MAXN], low[MAXN], belong[MAXN], sccCnt, dfsClock; stackint st; bool inSt[MAXN]; void tarjan(int u) { dfn[u] low[u] dfsClock; st.push(u); inSt[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (inSt[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { sccCnt; while (true) { int x st.top(); st.pop(); inSt[x] false; belong[x] sccCnt; if (x u) break; } } }这里判断“回边”的条件是inSt[v]而不是dfn[v]是否访问过。因为如果只是else if (dfn[v])会把已经出栈的SCC节点误当作回边来更新low导致错误。这是新手最容易踩的坑。dfn[v]是时间戳low[u]代表u能够回溯到的最早时间戳当low[u]dfn[u]时栈中从u开始到栈顶的所有点构成一个SCC。缩点后的DAG可以这样构建vectorint dag[MAXN]; bool visEdge[MAXN][MAXN]; // 防止重边 for (int u 1; u n; u) { for (int v : g[u]) { if (belong[u] ! belong[v]) { dag[belong[u]].push_back(belong[v]); } } }缩点后在DAG上可以做最长路、DP等操作很多“传播”“依赖”类题目都是这个套路。Tarjan还能顺手求割点和割边不过篇幅有限这里不展开核心逻辑类似。5. 匹配类与网络流模板5.1 匈牙利算法求二分图最大匹配二分图最大匹配是图论里的高频考点匈牙利算法是其中最经典、最好写的算法。它的本质是不断寻找增广路每找到一条增广路匹配数就加一。复杂度O(VE)但实际运行往往远快于这个上界。匈牙利算法模板vectorint g[MAXN]; // 左部点到右部点的边 int match[MAXN]; // 右部点匹配的左部点编号 bool vis[MAXN]; // 每次匹配中右部点是否被访问 bool dfs(int u) { for (int v : g[u]) { if (vis[v]) continue; vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } return false; } int hungarian(int n) { memset(match, -1, sizeof(match)); int res 0; for (int i 1; i n; i) { memset(vis, false, sizeof(vis)); if (dfs(i)) res; } return res; }这里的核心是match[v] -1 || dfs(match[v])。如果右部点v还没被匹配就直接匹配如果v已经被匹配了就尝试递归让已经匹配的左部点换一个右部点。这叫做“腾挪”。每一次dfs都会把vis数组清空防止在一条增广路中重复访问同一个右部点否则会死循环。使用匈牙利算法前要确保图确实是二分图。求二分图最大匹配还有一种方法叫Hopcroft-Karp复杂度O(E√V)但代码量大得多竞赛里通常用匈牙利就够。对于点特别多的场景可以再学Dinic跑二分图匹配。5.2 Dinic最大流模板核心网络流是图论中的高阶内容不过只要记住一个模板很多问题都能套。最大流最常用的算法是Dinic它结合了BFS分层和DFS增广。模板核心如下struct Edge { int to, next, cap; } edges[MAXM * 2]; // 每条边和反向边 int head[MAXN], cur[MAXN], cnt; int level[MAXN]; void addFlowEdge(int u, int v, int c) { edges[cnt] {v, head[u], c}; head[u] cnt; edges[cnt] {u, head[v], 0}; // 反向边容量0 } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; if (level[v] -1 edges[e].cap 0) { level[v] level[u] 1; q.push(v); } } } return level[t] ! -1; } int dfsFlow(int u, int t, int flow) { if (u t) return flow; for (int e cur[u]; e ! -1; e edges[e].next) { int v edges[e].to; if (level[v] level[u] 1 edges[e].cap 0) { int f dfsFlow(v, t, min(flow, edges[e].cap)); if (f 0) { edges[e].cap - f; edges[e ^ 1].cap f; return f; } } } return 0; } int dinic(int s, int t) { int flow 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(head)); while (true) { int f dfsFlow(s, t, INF); if (f 0) break; flow f; } } return flow; }这里有一个关键设计利用边序号从1开始、且反向边编号是正向边编号异或1e ^ 1的性质方便更新反向边。所以初始化时cnt必须从0或1开始并且保证每次加两条边。cur数组是当前弧优化用的避免DFS在已经无法增广的边上反复尝试这是Dinic能高效运行的重要原因。网络流模板背起来稍微费力但一旦出了“最大流”相关题目它能迅速派上用场。记住这个模板的框架很多变体费用流、最小割都只是在这个基础上加一些数组和条件。6. 常见问题与排查技巧实录6.1 边界条件和初始化问题我统计了自己刷图论题时遇到的bug超过一半都出在初始化和边界条件上。比如使用链式前向星时忘记memset(head, -1, sizeof(head))使用Dijkstra时遗忘memset(dist, 0x3f, sizeof(dist))使用并查集时忘记初始化parent[i] i。这些是低级错误但比赛时一紧张特别容易犯。建议每个模板都插入一个“reset”函数把所有全局数组在算法逻辑外重置一遍。例如我会在main函数里对每个算法单独封装成函数这样复用模板时只需调用一次不用到处找数组初始化位置。还有一个容易被忽略的边界问题是图的下标从0开始还是从1开始。如果题目给的节点编号是0到n-1而你模板写的1到n那么访问parent[0]可能导致越界。建议模板统一采用1-index在输入时把每个节点编号加1这样可以少很多麻烦。6.2 图论模板使用中的5个坑第一容器访问越界。使用vector邻接表时忘记把g开成MAXN或n1大小在访问g[n]时越界。第二双向边和单向边搞混。建无向图必须addEdge(u,v,w); addEdge(v,u,w);有些题目非常阴险要求建无向图但只写了“连接”你必须看清。第三重边处理。邻接矩阵存图时应该取min(g[u][v], w)链式前向星不需要去重因为算法本身能处理重边。但Kruskal时重边不影响结果。第四SPFA判断负环时把cnt[v]理解成入队次数还是松弛次数模板里用的是入队次数如果某点入队超过n次基本可以断定有负环。第五Floyd循环顺序不小心写成i,k,j导致结果错误这种错误很难通过小数据测试发现。以下是我整理的速查表问题现象可能原因排查方向答案比预期大边权初始化为0没有设置INF查看dist初始化赋值死循环未标记vis或标记错误检查DFS/BFS访问判断栈溢出递归深度过大改用显式栈或非递归写法Floyd结果完全不对k循环不在最外层调整循环顺序最大流输出为0反向边容量没设0或边的序号没用^1检查加边函数6.3 如何把模板变成自己的能力模板背下来不是目的能灵活运用才是。我有几个亲测有效的训练方法。第一个方法是默写。拿到一份模板后不要直接复制粘贴到编辑器先看着代码理解一遍然后合上文档自己从头写一遍。写错的地方就是你的薄弱点重点标记。第二个方法是变式训练。把Dijkstra改成求次短路把拓扑排序改成输出所有拓扑序把匈牙利算法改成求最小点覆盖。这些变式能让你理解模板里每个变量的作用而不是死记硬背。第三个方法是定期回顾。每两周抽时间把模板重新打一遍保持手感。我自己在准备竞赛的那段时间每道图论题做出来后都会对照模板检查是否能直接用模板快速解决。如果能说明题目核心是“模板题”如果不能我会把新思路加进模板的注释里。几个月后这套模板就成了我自己独有的武器遇到没见过的题也知道该往哪个方向改造。最后再分享一个小技巧人数比较少的图论题可以用暴力DFS先跑一遍验证自己理解的题意是否正确然后再用标准模板优化。比如判断两点之间是否存在路径直接BFS就能确认不用一上来就上Tarjan。模板是为你服务的不要被模板框住了思路。 图论算法模板大全：从建图到网络流，竞赛刷题必备
搞图论算法题最怕的不是思路难而是每次写代码都要重新从零敲一遍建图、DFS、最短路。明明都是些固定套路却因为某个细节写错浪费几个小时这种亏我吃过太多次。后来我把图论里常用到的算法模板整理成一套自己的代码库刷题时直接调省下的时间全用来想题目的核心逻辑。今天就把这套模板的核心思路和完整写法分享出来适合准备算法竞赛、刷LeetCode图论题、或者面试前突击图论的朋友参考。这套内容覆盖了图的存储、遍历、拓扑排序、最短路、最小生成树、连通性、二分图匹配和网络流这些常见高频考点。我不光会贴模板还会把每个模板背后“为什么要这么写”“哪些地方容易踩坑”讲清楚。你不需要全部背下来但建议把每段代码跑一遍改成自己的风格最后形成属于你自己的图论模板库。1. 图论模板的整体设计与思路拆解1.1 为什么竞赛与刷题需要“模板化”很多人觉得写算法题死记模板没出息但关键在于“模板化”和“背题”是两回事。图论问题千变万化但底层的基础操作极其固定。拿最短路来说无论题目如何包装最后解法的核心还是那几种算法。如果你能把这些基础算法写得又快又准就能把宝贵的比赛时间花在对题目的分析上而不是浪费在调试一眼就能看出的边界错误上。另外模板化的过程也是一个深度理解算法的过程。当你把Dijkstra、Tarjan这些算法亲手写成固定格式时你一定需要理解它的每一步在干什么。写完模板之后再遇到问题你的脑子里会直接浮现出这套代码结构做题速度会有质的提升。1.2 图论知识体系与模板分类图论的基础知识可以分为几个大的模块。第一个是存储结构包括邻接矩阵、邻接表、链式前向星。第二个是遍历包括深度优先搜索和广度优先搜索它们是很多图论算法的基础。第三个是路径问题包括单源最短路和全源最短路。第四个是生成树问题包括最小生成树和次小生成树。第五个是连通性问题包括并查集、强连通分量、割点、桥。第六个是匹配问题主要是二分图最大匹配。第七个是进阶的网络流问题最大流、费用流。我在整理模板时会按这个模块去分类。每个模块里的算法都有一份经过反复测试的代码需要时直接复制使用。下面我按照这个顺序把每个模板的关键代码和设计思路逐步拆给大家。2. 图的存储与遍历基础模板2.1 三种存图方式对比与选择存图是图论问题的第一步。这里我平时只考虑三种方式邻接矩阵、vector邻接表、链式前向星。邻接矩阵适合点少边多的稠密图点的数量在1000以内时很好用因为g[u][v] w可以直接判断两个点是否相连代码最简单。但一旦点数到10000以上矩阵的存储空间就是n^2级别会直接爆内存。vector邻接表是日常刷题最推荐的方式。用vectorpairint, int g[N]存带权图g[u].push_back({v, w})既能表示边的指向又能存边权写起来直观遍历也方便。不过vector在动态扩容时会有一定的性能损耗在一些对时间极度敏感的大型比赛中可能会比链式前向星慢一点。链式前向星是竞赛选手最常用的方式。它本质上是用数组模拟链表每个节点代表一条边通过head[u]找到的边索引再通过next指针遍历所有邻边。优点是可以静态分配内存遍历速度极快而且能够处理重边。缺点是可读性差一点写起来容易出错。我给出的模板是这样的const int MAXN 100005; // 点数 const int MAXM 200005; // 边数 struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], cnt 0; void addEdge(int u, int v, int w) { edges[cnt].to v; edges[cnt].w w; edges[cnt].next head[u]; head[u] cnt; } // 遍历u的所有邻边 for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; int w edges[e].w; }初始化时要把head数组全部置为-1。我看到很多新手会忘记这一步导致遍历时死循环或者数组越界。用memset(head, -1, sizeof(head))即可。至于选择策略如果你在竞赛中追求极致性能就用链式前向星如果是日常刷题或面试vector邻接表完全够用。2.2 DFS和BFS的模板写法深度优先搜索DFS和广度优先搜索BFS是图论算法里出现频率最高的遍历方式。DFS常用来做连通性检测、环检测、拓扑排序、Tarjan那类算法的基础BFS则常用于无权图最短路、层次遍历等场景。DFS递归模板很简单vectorint g[MAXN]; bool vis[MAXN]; void dfs(int u) { vis[u] true; // 处理当前节点的业务逻辑 for (int v : g[u]) { if (!vis[v]) { dfs(v); } } }这个模板需要注意的点是递归深度。当图是一条长度为10万的链时递归调用会导致栈溢出。这种时候需要改成显式栈stackint st; st.push(start); vis[start] true; while (!st.empty()) { int u st.top(); st.pop(); // 处理节点 for (int v : g[u]) { if (!vis[v]) { vis[v] true; st.push(v); } } }BFS模板同样基础却极其重要queueint q; vectorint dist(N, -1); dist[start] 0; q.push(start); while (!q.empty()) { int u q.front(); q.pop(); for (int v : g[u]) { if (dist[v] -1) { dist[v] dist[u] 1; q.push(v); } } }BFS最关键的设计是用dist[v] -1同时充当“是否访问过”和“距离”两个角色避免单独开一个visited数组。这也是图论模板里常见的“状态压缩”思路。对于无权图BFS天然能求单源最短路复杂度是O(VE)比Dijkstra还快。2.3 拓扑排序从队列到优先队列拓扑排序用于有向无环图DAG解决任务依赖、课程安排这类问题。核心思想是每次取一个入度为0的点删除它的所有出边更新其他点入度重复操作。如果最后取出的点数不等于总点数说明图中有环。普通拓扑排序模板Kahn算法vectorint g[MAXN]; int indeg[MAXN]; vectorint topo; // 存放拓扑序列 bool topoSort(int n) { queueint q; for (int i 1; i n; i) { if (indeg[i] 0) q.push(i); } while (!q.empty()) { int u q.front(); q.pop(); topo.push_back(u); for (int v : g[u]) { if (--indeg[v] 0) { q.push(v); } } } return (int)topo.size() n; }注意这里用--indeg[v] 0来判断比先减再判断更简洁。如果需要输出字典序最小的拓扑排序就把队列换成优先队列每次取出编号最小的入度为0的节点priority_queueint, vectorint, greaterint pq;这个变换在很多LeetCode题里都出现过比如“课程表II”要求返回字典序结果。模板里的优先队列用greaterint实现小根堆可以保证每次弹出的节点编号最小。这里还有个隐藏难点优先队列模板不能直接用于求“全局字典序最小”因为它只保证局部字典序最小但这个在拓扑排序场景下恰好等价于最终字典序最小因为每一步能取的节点中取最小的那个不会影响后续节点的可选性。3. 最短路算法模板3.1 Dijkstra堆优化模板与正确性Dijkstra算法处理的是非负权单源最短路问题。最经典的写法是用优先队列堆优化每次取出当前距离最小的点进行松弛。这里有一个非常容易出错的地方优先队列里可能会存同一个点的多个历史状态所以必须用vis数组去重避免同一个点被重复处理。堆优化的Dijkstra模板const int INF 0x3f3f3f3f; struct Node { int v, w; bool operator(const Node other) const { return w other.w; // 小根堆 } }; vectorNode g[MAXN]; int dist[MAXN]; bool vis[MAXN]; void dijkstra(int s) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; priority_queueNode pq; pq.push({s, 0}); while (!pq.empty()) { int u pq.top().v; pq.pop(); if (vis[u]) continue; vis[u] true; for (auto e : g[u]) { int v e.v; int w e.w; if (!vis[v] dist[v] dist[u] w) { dist[v] dist[u] w; pq.push({v, dist[v]}); } } } }代码中Node结构体里重载operator时取w other.w这是C优先队列默认大根堆的反向写法千万不要搞反。INF用0x3f3f3f3f而不是INT_MAX是因为0x3f3f3f3f加上一个权值不会溢出而且可以用memset按字节填充得到的就是0x3f3f3f3f非常方便。Dijkstra的正确性基于贪心思想已确定最短路的点集合中每次选距离最远的未确定点加入之后不会再被其他点更新。这个结论只有在所有边权非负时才成立。一旦出现负边堆优化Dijkstra就会失效必须改用SPFA或Bellman-Ford。3.2 SPFA与Bellman-Ford负环判断SPFA算法是Bellman-Ford的队列优化在稀疏图上表现很好最坏复杂度可能退化成O(VE)所以一些出题人会故意构造数据卡SPFA。虽然如此SPFA依然是处理负权边的最常用模板并且能判断负环。SPFA普通模板vectorpairint, int g[MAXN]; int dist[MAXN]; int cnt[MAXN]; // 记录每个点入队次数 bool inq[MAXN]; bool spfa(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(cnt, 0, sizeof(cnt)); memset(inq, false, sizeof(inq)); dist[s] 0; queueint q; q.push(s); inq[s] true; cnt[s] 1; while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (auto [v, w] : g[u]) { if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { q.push(v); inq[v] true; if (cnt[v] n) { return false; // 存在负环 } } } } } return true; }这里的cnt[v]表示点v入队的总次数如果某个点入队次数超过n点数说明图中存在负环。负环会让最短路不断变小所以必须判断并返回。SPFA还有一个常见优化SLFSmall Label First即如果当前节点距离小于队首距离则插到队首。在稀疏图上效果不错但也不是万能。我更推荐在非负权图里直接用Dijkstra只在有负权时才用SPFA。Bellman-Ford模板可以不写队列优化直接用n-1轮松弛for (int i 1; i n; i) { bool updated false; for (int e 1; e m; e) { int u edges[e].u, v edges[e].v, w edges[e].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; updated true; } } if (!updated) break; }第n轮如果还能松弛说明有负环。对于新手我建议直接背SPFA模板因为它在大多数情况下更快同时保留了Bellman-Ford的思路。3.3 Floyd全源最短路实现细节Floyd算法用于求任意两点间的最短路复杂度O(n^3)适合点数很小一般n300的场景。它的核心是动态规划思想int dis[MAXN][MAXN]; void floyd(int n) { for (int k 1; k n; k) { for (int i 1; i n; i) { if (dis[i][k] INF) continue; // 优化 for (int j 1; j n; j) { if (dis[i][j] dis[i][k] dis[k][j]) { dis[i][j] dis[i][k] dis[k][j]; } } } } }非常重要的一个细节是最外层循环必须是k也就是中间点。因为dis[i][j]的更新依赖于dis[i][k]和dis[k][j]只有先枚举中间点才能保证每个中间点的状态都已经被计算过。这个顺序错了结果就会错得离谱却很难发现。初始化时dis[i][i] 0其他不存在的边设为INF注意INF不能太大不然相加会溢出通常设置成0x3f3f3f3f约10^9就够了。Floyd还可以顺便求最小环做法是每次枚举中间点k之前检查dis[i][j] g[i][k] g[k][j]是否构成环这个进阶用法在遇到“求有向图最小环”的题目时很有用。4. 最小生成树与连通性模板4.1 Kruskal与Prim模板最小生成树问题最常用的是Kruskal算法因为它实现简单、复杂度优秀。核心思想是把所有边按权重从小到大排序然后依次加入边如果加入后不形成环就保留这条边。判断是否成环用并查集。Kruskal模板struct Edge { int u, v, w; bool operator(const Edge other) const { return w other.w; } } edges[MAXM]; int parent[MAXN]; int find(int x) { return parent[x] x ? x : parent[x] find(parent[x]); } int kruskal(int n, int m) { sort(edges 1, edges m 1); for (int i 1; i n; i) parent[i] i; int ans 0, cnt 0; for (int i 1; i m; i) { int ru find(edges[i].u); int rv find(edges[i].v); if (ru ! rv) { parent[ru] rv; ans edges[i].w; if (cnt n - 1) break; } } return cnt n - 1 ? ans : -1; // 返回-1表示图不连通 }注意find函数里用了路径压缩。parent[ru] rv也能用按秩合并优化但在路径压缩已经很快的前提下按秩合并不是必须的不过在极端数据下能进一步稳定复杂度。Prim算法则适合稠密图尤其是邻接矩阵存图时写起来非常简洁。它的思路是从一个点开始不断找离已选点集合最近的未选点加入。普通实现复杂度O(n^2)堆优化后是O((VE)logV)。竞赛中如果图是稠密的直接使用堆优化Prim。堆优化Prim模板priority_queueNode, vectorNode, greaterNode pq; bool vis[MAXN]; int dist[MAXN]; // 到当前生成树集合的最短距离 int prim(int s, int n) { memset(dist, 0x3f, sizeof(dist)); memset(vis, false, sizeof(vis)); dist[s] 0; int ans 0, cnt 0; pq.push({s, 0}); while (!pq.empty()) { auto [u, du] pq.top(); pq.pop(); if (vis[u]) continue; vis[u] true; ans du; cnt; for (auto e : g[u]) { int v e.v, w e.w; if (!vis[v] w dist[v]) { dist[v] w; pq.push({v, dist[v]}); } } } if (cnt ! n) return -1; return ans; }Prim算法容易犯的错误是忘记判断vis导致一个点被重复加入。模板中用if (vis[u]) continue剔除了堆里的过期节点这个和Dijkstra非常相似。4.2 并查集优化技巧并查集虽然不算单独的一类图论问题但它几乎出现在所有连通性相关的模板中。除了路径压缩还有一个重要的优化是“按秩合并”即让深度较小的树合并到深度较大的树上。路径压缩之后单独使用秩合并的意义会变小但两者结合可以让并查集的操作接近O(alpha(n))alpha是反阿克曼函数可以认为是一个常数。模板如下int parent[MAXN]; int rnk[MAXN]; void init(int n) { for (int i 1; i n; i) { parent[i] i; rnk[i] 1; } } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return 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; rnk[x] rnk[y]; }rnk存的是集合大小合并时让小集合挂到大集合下面。这样能够避免退化链的出现即使不路径压缩也能保持log级别的树高。日常写题时只用路径压缩通常也足够但把秩合并背下来可以应对刷题网站上的特殊构造数据。4.3 Tarjan求强连通分量与缩点强连通分量SCC是很多有向图问题的必经之路。Tarjan算法通过DFS的时间戳和栈来划分强连通分量。对于基于强连通分量的题目一般还要做“缩点”操作将所有SCC压缩成DAG上的一个点然后在DAG上做DP或拓扑排序。Tarjan模板vectorint g[MAXN]; int dfn[MAXN], low[MAXN], belong[MAXN], sccCnt, dfsClock; stackint st; bool inSt[MAXN]; void tarjan(int u) { dfn[u] low[u] dfsClock; st.push(u); inSt[u] true; for (int v : g[u]) { if (!dfn[v]) { tarjan(v); low[u] min(low[u], low[v]); } else if (inSt[v]) { low[u] min(low[u], dfn[v]); } } if (low[u] dfn[u]) { sccCnt; while (true) { int x st.top(); st.pop(); inSt[x] false; belong[x] sccCnt; if (x u) break; } } }这里判断“回边”的条件是inSt[v]而不是dfn[v]是否访问过。因为如果只是else if (dfn[v])会把已经出栈的SCC节点误当作回边来更新low导致错误。这是新手最容易踩的坑。dfn[v]是时间戳low[u]代表u能够回溯到的最早时间戳当low[u]dfn[u]时栈中从u开始到栈顶的所有点构成一个SCC。缩点后的DAG可以这样构建vectorint dag[MAXN]; bool visEdge[MAXN][MAXN]; // 防止重边 for (int u 1; u n; u) { for (int v : g[u]) { if (belong[u] ! belong[v]) { dag[belong[u]].push_back(belong[v]); } } }缩点后在DAG上可以做最长路、DP等操作很多“传播”“依赖”类题目都是这个套路。Tarjan还能顺手求割点和割边不过篇幅有限这里不展开核心逻辑类似。5. 匹配类与网络流模板5.1 匈牙利算法求二分图最大匹配二分图最大匹配是图论里的高频考点匈牙利算法是其中最经典、最好写的算法。它的本质是不断寻找增广路每找到一条增广路匹配数就加一。复杂度O(VE)但实际运行往往远快于这个上界。匈牙利算法模板vectorint g[MAXN]; // 左部点到右部点的边 int match[MAXN]; // 右部点匹配的左部点编号 bool vis[MAXN]; // 每次匹配中右部点是否被访问 bool dfs(int u) { for (int v : g[u]) { if (vis[v]) continue; vis[v] true; if (match[v] -1 || dfs(match[v])) { match[v] u; return true; } } return false; } int hungarian(int n) { memset(match, -1, sizeof(match)); int res 0; for (int i 1; i n; i) { memset(vis, false, sizeof(vis)); if (dfs(i)) res; } return res; }这里的核心是match[v] -1 || dfs(match[v])。如果右部点v还没被匹配就直接匹配如果v已经被匹配了就尝试递归让已经匹配的左部点换一个右部点。这叫做“腾挪”。每一次dfs都会把vis数组清空防止在一条增广路中重复访问同一个右部点否则会死循环。使用匈牙利算法前要确保图确实是二分图。求二分图最大匹配还有一种方法叫Hopcroft-Karp复杂度O(E√V)但代码量大得多竞赛里通常用匈牙利就够。对于点特别多的场景可以再学Dinic跑二分图匹配。5.2 Dinic最大流模板核心网络流是图论中的高阶内容不过只要记住一个模板很多问题都能套。最大流最常用的算法是Dinic它结合了BFS分层和DFS增广。模板核心如下struct Edge { int to, next, cap; } edges[MAXM * 2]; // 每条边和反向边 int head[MAXN], cur[MAXN], cnt; int level[MAXN]; void addFlowEdge(int u, int v, int c) { edges[cnt] {v, head[u], c}; head[u] cnt; edges[cnt] {u, head[v], 0}; // 反向边容量0 } bool bfs(int s, int t) { memset(level, -1, sizeof(level)); queueint q; level[s] 0; q.push(s); while (!q.empty()) { int u q.front(); q.pop(); for (int e head[u]; e ! -1; e edges[e].next) { int v edges[e].to; if (level[v] -1 edges[e].cap 0) { level[v] level[u] 1; q.push(v); } } } return level[t] ! -1; } int dfsFlow(int u, int t, int flow) { if (u t) return flow; for (int e cur[u]; e ! -1; e edges[e].next) { int v edges[e].to; if (level[v] level[u] 1 edges[e].cap 0) { int f dfsFlow(v, t, min(flow, edges[e].cap)); if (f 0) { edges[e].cap - f; edges[e ^ 1].cap f; return f; } } } return 0; } int dinic(int s, int t) { int flow 0; while (bfs(s, t)) { memcpy(cur, head, sizeof(head)); while (true) { int f dfsFlow(s, t, INF); if (f 0) break; flow f; } } return flow; }这里有一个关键设计利用边序号从1开始、且反向边编号是正向边编号异或1e ^ 1的性质方便更新反向边。所以初始化时cnt必须从0或1开始并且保证每次加两条边。cur数组是当前弧优化用的避免DFS在已经无法增广的边上反复尝试这是Dinic能高效运行的重要原因。网络流模板背起来稍微费力但一旦出了“最大流”相关题目它能迅速派上用场。记住这个模板的框架很多变体费用流、最小割都只是在这个基础上加一些数组和条件。6. 常见问题与排查技巧实录6.1 边界条件和初始化问题我统计了自己刷图论题时遇到的bug超过一半都出在初始化和边界条件上。比如使用链式前向星时忘记memset(head, -1, sizeof(head))使用Dijkstra时遗忘memset(dist, 0x3f, sizeof(dist))使用并查集时忘记初始化parent[i] i。这些是低级错误但比赛时一紧张特别容易犯。建议每个模板都插入一个“reset”函数把所有全局数组在算法逻辑外重置一遍。例如我会在main函数里对每个算法单独封装成函数这样复用模板时只需调用一次不用到处找数组初始化位置。还有一个容易被忽略的边界问题是图的下标从0开始还是从1开始。如果题目给的节点编号是0到n-1而你模板写的1到n那么访问parent[0]可能导致越界。建议模板统一采用1-index在输入时把每个节点编号加1这样可以少很多麻烦。6.2 图论模板使用中的5个坑第一容器访问越界。使用vector邻接表时忘记把g开成MAXN或n1大小在访问g[n]时越界。第二双向边和单向边搞混。建无向图必须addEdge(u,v,w); addEdge(v,u,w);有些题目非常阴险要求建无向图但只写了“连接”你必须看清。第三重边处理。邻接矩阵存图时应该取min(g[u][v], w)链式前向星不需要去重因为算法本身能处理重边。但Kruskal时重边不影响结果。第四SPFA判断负环时把cnt[v]理解成入队次数还是松弛次数模板里用的是入队次数如果某点入队超过n次基本可以断定有负环。第五Floyd循环顺序不小心写成i,k,j导致结果错误这种错误很难通过小数据测试发现。以下是我整理的速查表问题现象可能原因排查方向答案比预期大边权初始化为0没有设置INF查看dist初始化赋值死循环未标记vis或标记错误检查DFS/BFS访问判断栈溢出递归深度过大改用显式栈或非递归写法Floyd结果完全不对k循环不在最外层调整循环顺序最大流输出为0反向边容量没设0或边的序号没用^1检查加边函数6.3 如何把模板变成自己的能力模板背下来不是目的能灵活运用才是。我有几个亲测有效的训练方法。第一个方法是默写。拿到一份模板后不要直接复制粘贴到编辑器先看着代码理解一遍然后合上文档自己从头写一遍。写错的地方就是你的薄弱点重点标记。第二个方法是变式训练。把Dijkstra改成求次短路把拓扑排序改成输出所有拓扑序把匈牙利算法改成求最小点覆盖。这些变式能让你理解模板里每个变量的作用而不是死记硬背。第三个方法是定期回顾。每两周抽时间把模板重新打一遍保持手感。我自己在准备竞赛的那段时间每道图论题做出来后都会对照模板检查是否能直接用模板快速解决。如果能说明题目核心是“模板题”如果不能我会把新思路加进模板的注释里。几个月后这套模板就成了我自己独有的武器遇到没见过的题也知道该往哪个方向改造。最后再分享一个小技巧人数比较少的图论题可以用暴力DFS先跑一遍验证自己理解的题意是否正确然后再用标准模板优化。比如判断两点之间是否存在路径直接BFS就能确认不用一上来就上Tarjan。模板是为你服务的不要被模板框住了思路。