平时帮人复盘图论基础题错因，我发现一个特别普遍的现象：很多人不是不会写代码，而是面对题目里的图时，脑子里没有一条清晰的“识别路径”。看到题目第一反应永远是“这题该用哪个算法”，而不是先问自己“这张图长什么样、边有没有方向、有没有环、存成什么结构最舒服”。图论基础阶段的练习，核心其实就三件事：看懂图、存好图、选对遍历方式。这篇习题集锦就是按这个思路整理的，从图的表示、DFS/BFS，到最短路径、最小生成树、拓扑排序这些经典题型，每一类都配了思路拆解和易踩的坑，适合正在补图论基础的学生，也适合把算法模板背了一堆但一做题就发懵的开发者。
1. 图的表示与基本概念：先把“存图”这一关过了
1.1 概念判断类习题：度、握手定理与图是否存在的判定
图论基础阶段最容易丢分的，往往不是算法题，而是概念判断题。比如给你一个图形的顶点度数列表，让你判断这样的图到底存不存在，这种题看起来简单，但很多人一紧张就忘掉最基本的握手定理。
握手定理的内容非常朴素：无向图中所有顶点的度数之和等于边数的两倍。为什么？因为每条边贡献两个端点，每个端点贡献1度，一条边总共贡献2度。所以度数和永远是偶数。这个定理的推论“奇数度顶点的个数一定是偶数”更是高频考点，很多题绕个弯就是考它。
经典习题1：是否存在一个有5个顶点、且每个顶点度数都是奇数的无向图？答案是不存在。如果5个顶点全是奇数度，那度数和就是5个奇数相加，结果一定是奇数，但度数和必须为偶数，直接矛盾。这类题的价值在于，它逼着你形成“看到度就想到度数和”的条件反射，而不是拿到题就瞎猜。
经典习题2：某无向图有12个顶点、20条边，已知其中10个顶点的度数之和为30，求剩余2个顶点的度数之和。解起来很简单：度数和等于40，剩余2个顶点度数和就是40减30等于10。这种题在考试和面试里的出现率很高，本质就是考察握手定理有没有真正进脑子。
我的训练建议是：把这三类小题当“口算题”反复练。第一类是给一张具体图形，判断它是不是简单图、完全图、二分图、正则图；第二类是给一个度数序列，判断能否构成无向图；第三类是给有向图的出度入度表，推算边数并判断是否存在欧拉通路。这些题目都不难，但能把基本概念的肌肉记忆练出来，后面学所有算法都会更顺。
1.2 邻接矩阵还是邻接表，数据范围说了算
很多图论题连算法都算不上，纯粹是考“你会不会读图”。如果存储方式选错，后面的算法写得再漂亮也没用。
邻接矩阵就是一个二维数组，graph[u][v]直接表示点 u 到点 v 是否有边。优点是查询任意两点之间是否有边的复杂度是 O(1)，写起来最无脑；缺点是空间复杂度 O(V²)，顶点数稍微上来就爆内存。
邻接表呢，是用一个数组，每个元素是一个列表，adj[u]存 u 能到达的所有邻居。优点是空间复杂度 O(V+E)，遍历邻居时效率高；缺点是判断两点之间是否有边需要遍历邻居列表，不太适合“频繁查询任意两点关系”的场景。
我做题时基本按这张表来选：
| 数据规模 | 推荐存储方式 | 原因 |
|---|---|---|
| 顶点数 ≤ 100 | 邻接矩阵 | 实现简单，调试直观 |
| 顶点数到 10⁵、边稀疏 | 邻接表 | 省空间，遍历快 |
| 需要频繁判断“任意两点是否有边” | 邻接矩阵 | 查询 O(1) |
| 做 Kruskal 最小生成树 | 边列表 | 要按边权排序，不依赖邻接关系 |
邻接表写起来很固定，无向图记得加反向边：
adj = [[] for _ in range(n)] for u, v in edges: adj[u].append(v) adj[v].append(u) # 无向图必须加反向边有一个新手最容易犯的错：开了一个int graph[100000][100000]这么大的二维数组，程序直接编译不过。所以做题第一步不是建图，而是看数据范围。数据范围既决定了存储方式，也决定了算法选择，这点在后面的最短路径部分还会反复出现。
1.3 专项练习：手动推演 DFS/BFS 访问顺序
有一类基础题基本是图论入门必考：给定一张图和起始点，写出深度优先搜索和广度优先搜索的访问顺序。这种题看着没有技术含量，但极其容易因为一个小细节翻车。
翻车的核心原因在于：访问顺序依赖“邻居列表的顺序”。如果题目输入边的时候是乱序的，而你默认按编号升序来遍历，那结果必然和标准答案对不上。另一个常见问题是，DFS 到底是“先标记再递归”还是“先递归再标记”，BFS 到底是“入队时标记”还是“出队时标记”，写出来的输出顺序完全不同。
我自己的训练方法是：拿到这种题，先在草稿纸上把邻接表列出来，明确排序规则，再手动推一遍。如果答案不一致，不要急着怀疑标准答案，先检查自己的邻居列表顺序是不是和题目输入的建图顺序一致。手推的过程看起来笨，但特别训练“程序执行感”。真正面试或者竞赛的时候，考官可能会直接在白板上画一张图让你口述遍历过程，这时候手推能力比会背模板有用得多。
2. DFS/BFS 专项：遍历顺序、连通性与环检测
2.1 递归实现里的隐形栈与显式栈
DFS 和 BFS 是图论里用得最多的两个基础算法，不理解它们的执行细节，后面学连通分量、拓扑排序、二分图判定都会非常吃力。
先看 DFS。递归写法最常见：
visited = set() def dfs(u): visited.add(u) for v in adj[u]: if v not in visited: dfs(v)递归版本本质上是在用系统调用栈，好处是代码短、好理解；坏处是如果图很深，比如一条链上有 10⁵ 个顶点，递归深度可能直接让程序栈溢出。我遇到过很多次类似情况：本地跑小样例没事，一提交大数据就段错误。解法就是把 DFS 改成显式栈，用stack.append和stack.pop()模拟递归的过程；或者提高递归深度限制，某些语言里可以，但最好还是养成习惯，提前评估树深。
BFS 用队列实现：起点入队，出队时把未访问的邻居全部入队。这里有个关键细节：要在“入队时标记”，而不是“出队时标记”。如果出队时才标记某个顶点已访问，可能在它还没出队前就被重复入队很多次，导致队列爆炸。
from collections import deque def bfs(start): visited = set([start]) q = deque([start]) while q: u = q.popleft() for v in adj[u]: if v not in visited: visited.add(v) q.append(v)2.2 判环练习：父节点与递归栈
环检测是 DFS 的经典应用。无向图和有向图的判环思路完全不同，这也是一个特别容易踩坑的地方。
无向图判环有个注意点：当 DFS 遍历到邻居时，要跳过父节点，否则会把一条无向边误判成环。例如从节点0到节点1，再从1发现邻居0，如果不知道0是父节点，就会认为找到环了，但事实上这只是一条普通边。
def dfs_no_cycle(u, parent): visited[u] = True for v in adj[u]: if not visited[v]: if dfs_no_cycle(v, u): return True elif v != parent: return True return False有向图判环更麻烦，不能只开一个 visited 数组，还需要一个“递归栈”标记，表示这个点当前是否还在 DFS 的调用链上。只有遇到一个“已经访问过且还在调用链上”的顶点，才算有环。
visited = [False] * n in_stack = [False] * n def dfs_cycle(u): visited[u] = True in_stack[u] = True for v in adj[u]: if not visited[v]: if dfs_cycle(v): return True elif in_stack[v]: return True in_stack[u] = False return False这个 in_stack 的设计是很多入门者不太理解的地方。朴素直觉会问：visited 为 True 不就行了吗，为什么要多一个栈标记？因为有向图里，你访问过的点可能早就递归结束了，它并不在当前路径上。比如 A 指向 B，再指向 C，然后有一条边从 C 回到 A，这是环；但如果有一条边从 C 回到 B，而 B 已经递归完了，就不是“在这个 DFS 路径上重新遇到”，需要输出有向无环图的拓扑排序时，这种区分是生死攸关的。
2.3 连通分量题型：从“省份数量”到“岛屿数量”
连通分量题是 DFS/BFS 最自然的应用，也是很多“换皮题”的底层模型。
最经典的练习是 LeetCode 200 题“岛屿数量”：一个二维矩阵里，1 表示陆地，0 表示水，上下左右连起来的 1 算一个岛，要你数有多少个岛。这题本质就是在求一个网格图的连通分量数量，只是节点和边没有显式地给你。做法就是遍历所有格子，遇到没访问过的1就开始 DFS/BFS，把能连到的所有1都标记访问，计数器加一。
同类型题还有“省份数量”：n 个城市，给你一个邻接矩阵表示城市间的朋友关系，求有多少个朋友圈。这个更直接，连建图都省了。
我的建议是做完 DFS 版本，再用 BFS 写一遍，最后再用并查集写一遍。同一个题用三种解法各做一遍，比换着做三个题印象深得多。连通分量这块写熟了，“选 DFS 还是选 BFS”就不会再纠结，因为你会发现大多数场景下它俩都能用，只是在额外信息（比如最短路）上才有明显差异。
3. 最短路径与最小生成树：先把原理吃透再背模板
3.1 Dijkstra 的贪心前提，以及一个让它失效的反例
Dijkstra 是单源最短路径问题里最高频的算法，但很多初学者只背了优先队列模板，一旦问“为什么它不能处理负权边”，就答不上来。
Dijkstra 的核心是贪心：每次从“还没确定最短距离”的点里，取出当前距离最小的点 u，认为 u 的最短距离已经不可能再变小了，然后用 u 去松弛邻居。这个逻辑成立的前提是什么？所有边的权值非负。因为只有非负，已经取出的最小距离点才不可能通过绕路变得更短——绕路只会增加距离。
负权边会打破这个逻辑。举一个经典反例：有向图有三个顶点 s、a、b，三条边分别是 s→a 权值 1，s→b 权值 2，b→a 权值 -2。从 s 出发，正确的 s 到 a 的最短距离是多少？是走 s→b→a，距离 2+(-2)=0，比 s→a 的 1 更短。但 Dijkstra 会怎么跑呢？一开始 dist[s]=0，dist[a]=1，dist[b]=2，选择距离最小的 a，把 dist[a]=1 当成最终结果；后面取出 b，能把 a 更新成 0，但 a 已经被标记为访问过了，更新被忽略。最终输出 1，而正确答案是 0，算法失败。
这类反例练习非常值得做。它的价值在于逼着你想明白“贪心到底贪在哪一步”，以及“什么条件下贪心是安全的”。弄懂了这一点，你才算真正会了 Dijkstra，而不是只会套模板。
3.2 Bellman-Ford 与 Floyd：什么时候换赛道
既然 Dijkstra 处理不了负权边，那负权边场景该用什么？基础课程里一般会介绍 Bellman-Ford。它的思路是对所有边做 V-1 轮松弛，因为一条简单路径最多经过 V-1 条边，每轮至少能让一条最短路径确定下来。做完 V-1 轮之后，如果第 V 轮还能继续松弛，就说明图里有负环——负环意味着最短路可以无限变小。
弗洛伊德算法则是另一种思路，解决的是多源最短路问题，也就是要求“任意两点之间”的最短距离。它的代码很短，三层循环，核心转移方程就是：
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])时间复杂度 O(V³)，所以只适合 V 在几百以内的题目。关于 Floyd，我特别建议做一件事：亲手拿一张 4 节点的图，把三层循环的中间过程完整推一遍。过程虽然繁琐，但你会突然理解它为什么是动态规划，以及为什么最外层必须是中间点 k。这个理解比背十遍模板都有用。
| 算法 | 适用场景 | 时间复杂度 |
|---|---|---|
| Dijkstra | 单源最短路，边权非负 | O(E log V) |
| Bellman-Ford | 单源最短路，可处理负权 | O(VE) |
| Floyd-Warshall | 任意两点最短路，节点少 | O(V³) |
3.3 最小生成树：Kruskal 为什么更受考场欢迎
最小生成树两大经典算法，Kruskal 和 Prim。Kruskal 的思路非常直接：把所有边按权值从小到大排序，每次取最小边，如果这条边的两个端点当前不在同一个连通块里，就选择它，并合并两个连通块。这个过程用到并查集，代码写起来很套路。
edges.sort(key=lambda e: e[2]) parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x def union(x, y): rx, ry = find(x), find(y) if rx == ry: return False parent[rx] = ry return True ans = 0 cnt = 0 for u, v, w in edges: if union(u, v): ans += w cnt += 1 if cnt == n - 1: break为什么我一般推荐基础阶段优先写 Kruskal？因为它思路直观，只需要把边排序，然后用并查集处理连通性，代码不容易写错。Prim 虽然在某些稠密图场景更优，但实现细节更多，优先级队列加松弛的逻辑初学时容易绕晕。
练习题建议：给一张 6 节点带权无向图，让你求最小生成树总权值。注意，当出现多条权值相同的边时，最小生成树可能不唯一，但总权值一定是唯一的。有人会纠结“为什么答案和我写的边不一样”，其实只要总权值一致，树的结构不同完全正常。
4. 进阶题型三大金刚：二分图、欧拉回路、拓扑排序
4.1 染色法判定二分图：把“关系”抽象成“可二分性”
二分图是图论里非常优美的结构：所有顶点能分成两个集合，使得每条边的两个端点各在其中一个集合里。几乎所有的“二分”类问题，比如把一群人分成两组、让朋友不在同一组、把课程分成两个学期，本质都是在判二分图。
判定方法叫染色法。从某个顶点开始，把它染成颜色0，然后 BFS 或 DFS 遍历，邻居必须染成颜色1；如果遇到一个已经被染色的邻居，颜色却和自己相同，那就不可能是二分图。
color = [-1] * n def is_bipartite(start): color[start] = 0 q = deque([start]) while q: u = q.popleft() for v in adj[u]: if color[v] == -1: color[v] = 1 - color[u] q.append(v) elif color[v] == color[u]: return False return True这个题我也推荐对比着 DFS 写一遍，因为染色法对遍历方式并不挑剔。真正的易错点是一张图可能不连通，你需要遍历所有连通分量，逐一判断，而不是只跑一个起点就结束。
4.2 一笔画与欧拉回路：存在性条件比路线更重要
“一笔画”问题在图论里对应的是欧拉通路和欧拉回路。欧拉回路的判定条件非常干脆：一个无向连通图存在欧拉回路，当且仅当所有顶点的度数都是偶数。存在欧拉通路（不一定回到起点）的条件则是：奇数度顶点个数为0或2。
最经典的题目就是七桥问题。四块陆地对应四个顶点，七座桥对应七条边，你把度数一算，四个顶点全是奇数度，所以不可能一次不重复地走完所有桥。这个题放到现在看很入门，但它就是图论这门学科的起点。
进阶一点的练习题是：给出一个有向图，判断是否存在欧拉回路。有向图的条件换成：所有顶点入度等于出度，并且忽略边方向后图是连通的。很多人在这个“忽略方向后连通”的细节上出错，只看入度出度相等，却忘了顶点可能根本不在一个连通块里。
4.3 拓扑排序：DAG、入度表和课程表问题
拓扑排序解决的是有向无环图的排序问题：把顶点排成一个序列，使得所有边都从序列前面指向后面。这个结构天然对应“依赖关系”，比如课程先修、项目构建依赖、编译顺序。
标准做法是 Kahn 算法：统计每个顶点的入度，把入度为0的顶点先入队；出队时把它所有邻居的入度减1，一旦某个邻居入度变成0就入队。最后如果入队的顶点数少于总顶点数，说明图里有环，不存在拓扑排序。
indeg = [0] * n for u, v in edges: # 有向边 u -> v indeg[v] += 1 q = deque([i for i in range(n) if indeg[i] == 0]) res = [] while q: u = q.popleft() res.append(u) for v in adj[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) if len(res) < n: print("存在环，无拓扑排序") else: print(res)LeetCode 的课程表系列题就是这个问题的换皮：有 n 门课，给你先修关系，问能否把所有课修完，以及输出一种学习顺序。第一问就是判环，第二问就是输出拓扑序。做这个题时，一定要把“入度表”和“邻接表”分离清楚，很多人把边方向建反，导致输出完全错误。
5. 写图论题最容易翻车的五个边界细节
5.1 孤立点、自环与多重边
图论题里的输入数据从来不像教材那么干净。孤立点不连接任何边，很多算法会漏掉它们，比如求连通分量时忘了访问孤立点。自环是一条边连接同一个顶点，无向图自环给该顶点贡献2度，有向图自环让入度和出度各加1。多重边则是两个顶点之间有多条边，判断有没有环时，多重边可能被误判成环。应对方法就是读题时先问三件事：有没有孤立点、允不允许自环、两个点之间会不会有多条边。
5.2 有向图与无向图的初始化差异
无向图建邻接表要加双向边，有向图只加单向边。这话听着像废话，但真到做题时，因为忘加反向边导致的错误占图论基础 bug 的大头。建议建图之后先打印一遍邻接表，肉眼确认边数和方向是否正确，再往下写算法。
5.3 递归深度与栈溢出
DFS 用递归写很方便，但一旦图是一条长链，递归深度达到几十万层，程序就会崩。要么改成显式栈，要么用 BFS，要么在最前面设置递归深度限制。我见过很多次“本地没问题、提交就溢出”的情况，问题就出在这里。
5.4 距离初始化的“无穷大”选择
最短路算法里的无穷大不能随便写。做加法时，INT_MAX这种值加上一个正数会溢出成负数，反而导致错误更新。常见的做法是取0x3f3f3f3f，这个值足够大，两个它相加也不会溢出 int。这些小细节在算法题里非常常见，但基础教材很少专门提。
5.5 邻接表顺序导致遍历结果不一致
同样一张图，按输入顺序建表和按顶点编号排序建表，DFS/BFS 的输出顺序可能完全不同。所以很多遍历类题目会明确说明“按编号从小到大访问邻居”。没有说明时，标准答案通常按输入顺序，把自己建的邻接表顺序和题目顺序对齐，是一个值得养成的习惯。
6. 图论刷题路线：从基础到进阶怎么推进
6.1 我自己带训练时常用的顺序
如果你刚接触图论，最忌直接跳到困难题。我一般建议按这个顺序推进：
- 基础概念判断与图的存储：先做一二十道“建图 + 遍历顺序”的题，把邻接表写熟。
- DFS/BFS 连通分量：做一遍“岛屿数量”“省份数量”，熟悉图和棋盘网格之间的转换。
- 判环与拓扑排序：写课程表系列题，理解有向图的依赖关系。
- 最短路三件套：Dijkstra、Bellman-Ford、Floyd 各找两三道模板题，亲手构造反例。
- 最小生成树：Kruskal 模板题刷熟，并查集顺手就练了。
- 二分图染色和欧拉回路：这类题量不大，但思路独特，适合用来打开视野。
每类至少做两三道题再进入下一类，不要只做一道就去“速通”算法清单。图论题最重要的就是重复，同样的算法写三遍，印象才会真正沉淀下来。
6.2 错题复盘时，一定要把图画出来
每做完一道图论题，我都建议在草稿纸上把这个图重画一遍。画图的动作不是浪费时间，它是在逼你把抽象的边和点变成视觉结构。看到图以后，你会更快判断出这是一道最短路题、最小生成树题还是拓扑排序题。
对我个人来说，图论水平的提高并不来自刷题数量，而来自“每次做错以后，能不能把自己重新放进那道题的图里”。如果你能把常见的图形结构看熟了——树、环、二分图、DAG、稀疏图、稠密图，遇到新题时自然能认出它的本质。这也是“图论及其应用”这门课最想传达的东西：图论不只是数学概念，它是一种建模工具，把乱七八糟的现实关系简化成顶点和边，再用算法去回答你真正关心的问题。
最后分享一个我自己一直用的复习习惯：把做过题的题干缩写成一句话，记在一个笔记里，不写解法，只写“这道题考了哪张图、哪种遍历、哪个算法”。过两周再去看这句话，如果还能准确说出解法，这个知识点才算真正掌握了。用这个方法复习图论，比反复刷同一套卷子效率高不少。
