搞图论算法题，最怕的不是思路难，而是每次写代码都要重新从零敲一遍建图、DFS、最短路。明明都是些固定套路，却因为某个细节写错浪费几个小时，这种亏我吃过太多次。后来我把图论里常用到的算法模板整理成一套自己的代码库，刷题时直接调，省下的时间全用来想题目的核心逻辑。今天就把这套模板的核心思路和完整写法分享出来，适合准备算法竞赛、刷LeetCode图论题、或者面试前突击图论的朋友参考。
这套内容覆盖了图的存储、遍历、拓扑排序、最短路、最小生成树、连通性、二分图匹配和网络流这些常见高频考点。我不光会贴模板，还会把每个模板背后“为什么要这么写”“哪些地方容易踩坑”讲清楚。你不需要全部背下来，但建议把每段代码跑一遍，改成自己的风格，最后形成属于你自己的图论模板库。
1. 图论模板的整体设计与思路拆解
1.1 为什么竞赛与刷题需要“模板化”
很多人觉得写算法题死记模板没出息，但关键在于“模板化”和“背题”是两回事。图论问题千变万化，但底层的基础操作极其固定。拿最短路来说，无论题目如何包装，最后解法的核心还是那几种算法。如果你能把这些基础算法写得又快又准，就能把宝贵的比赛时间花在对题目的分析上，而不是浪费在调试一眼就能看出的边界错误上。
另外，模板化的过程也是一个深度理解算法的过程。当你把Dijkstra、Tarjan这些算法亲手写成固定格式时，你一定需要理解它的每一步在干什么。写完模板之后再遇到问题，你的脑子里会直接浮现出这套代码结构，做题速度会有质的提升。
1.2 图论知识体系与模板分类
图论的基础知识可以分为几个大的模块。第一个是存储结构，包括邻接矩阵、邻接表、链式前向星。第二个是遍历，包括深度优先搜索和广度优先搜索，它们是很多图论算法的基础。第三个是路径问题，包括单源最短路和全源最短路。第四个是生成树问题，包括最小生成树和次小生成树。第五个是连通性问题，包括并查集、强连通分量、割点、桥。第六个是匹配问题，主要是二分图最大匹配。第七个是进阶的网络流问题，最大流、费用流。
我在整理模板时，会按这个模块去分类。每个模块里的算法都有一份经过反复测试的代码，需要时直接复制使用。下面我按照这个顺序，把每个模板的关键代码和设计思路逐步拆给大家。
2. 图的存储与遍历基础模板
2.1 三种存图方式对比与选择
存图是图论问题的第一步。这里我平时只考虑三种方式：邻接矩阵、vector邻接表、链式前向星。
邻接矩阵适合点少边多的稠密图，点的数量在1000以内时很好用，因为g[u][v] = w可以直接判断两个点是否相连，代码最简单。但一旦点数到10000以上，矩阵的存储空间就是n^2级别，会直接爆内存。
vector邻接表是日常刷题最推荐的方式。用vector<pair<int, 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递归模板很简单：
vector<int> g[MAXN]; bool vis[MAXN]; void dfs(int u) { vis[u] = true; // 处理当前节点的业务逻辑 for (int v : g[u]) { if (!vis[v]) { dfs(v); } } }这个模板需要注意的点是递归深度。当图是一条长度为10万的链时，递归调用会导致栈溢出。这种时候需要改成显式栈：
stack<int> 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模板同样基础，却极其重要：
queue<int> q; vector<int> 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(V+E)，比Dijkstra还快。
2.3 拓扑排序：从队列到优先队列
拓扑排序用于有向无环图（DAG），解决任务依赖、课程安排这类问题。核心思想是每次取一个入度为0的点，删除它的所有出边，更新其他点入度，重复操作。如果最后取出的点数不等于总点数，说明图中有环。
普通拓扑排序模板（Kahn算法）：
vector<int> g[MAXN]; int indeg[MAXN]; vector<int> topo; // 存放拓扑序列 bool topoSort(int n) { queue<int> 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_queue<int, vector<int>, greater<int>> pq;这个变换在很多LeetCode题里都出现过，比如“课程表II”要求返回字典序结果。模板里的优先队列用greater<int>实现小根堆，可以保证每次弹出的节点编号最小。这里还有个隐藏难点：优先队列模板不能直接用于求“全局字典序最小”，因为它只保证局部字典序最小，但这个在拓扑排序场景下恰好等价于最终字典序最小，因为每一步能取的节点中，取最小的那个不会影响后续节点的可选性。
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; // 小根堆 } }; vector<Node> 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_queue<Node> 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普通模板：
vector<pair<int, 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; 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 &[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还有一个常见优化：SLF（Small 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)，适合点数很小（一般n<=300）的场景。它的核心是动态规划思想：
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((V+E)logV)。竞赛中如果图是稠密的，直接使用堆优化Prim。
堆优化Prim模板：
priority_queue<Node, vector<Node>, greater<Node>> 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模板：
vector<int> g[MAXN]; int dfn[MAXN], low[MAXN], belong[MAXN], sccCnt, dfsClock; stack<int> 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可以这样构建：
vector<int> 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)，但实际运行往往远快于这个上界。
匈牙利算法模板：
vector<int> 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)); queue<int> 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开始、且反向边编号是正向边编号异或1（e ^ 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或n+1大小，在访问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。模板是为你服务的，不要被模板框住了思路。
