图论入门：邻接表与DFS/BFS遍历实战要点

day48，训练营推进到了图论专题1。前47天基本在数组、链表、哈希、栈队列和动态规划里打转，做题模式相对固定，突然切换到图论，很多人第一反应是：这该不会又是一堆背模板的题目吧？实际上图论入门专题的代码并不复杂，真正难的是把实际问题抽象成图，再决定用什么存储结构、走DFS还是BFS。

这篇手记不打算从头抄一遍教材知识点，我从当天打卡遇到的几个真实问题出发，把邻接表与邻接矩阵怎么选、DFS与BFS模板怎么写、以及那些动不动就让人调试半小时的细节一次性说清楚。如果你正在准备校招笔试、机试，或者刚开始刷图论题，这篇应该能帮你省下不少绕弯的时间。

1. 图论专题1到底在考什么：先看清考点地图再动手

1.1 图的四要素：顶点、边、方向和权值

学图论最容易犯的第一个错误，是还没分清概念就开始敲代码。图论里的图不是图片，而是由顶点（vertex）和边（edge）组成的结构。拿公路网举例，城市是顶点，道路是边。每条路都是双向的，这是无向图；只能单向通行，就是有向图；如果边上还挂着长度或通行费用，那就是带权图。生活中大多数场景天然是图：好友关系、网页跳转链接、地铁换乘线路，只要能抽象成顶点和边，问题就能搬到图算法这一整套方法论里处理。

代码层面常常只需要一个二维结构来表达。有的题目直接给出N个点和M条边，输入形如“a b”，代表a和b之间存在一条边。这时候你要在脑子里立刻翻译成邻接表或邻接矩阵。另外还有几个词必须考前就扎稳：度，无向图里一个点有几条边；入度与出度，有向图里分别指指向它的边数和它指出的边数；路径、回路、连通。这些术语看着基础，却是后面判断孤立点、重边、自环时能否快速反应的前提。

1.2 训练营题目大致覆盖的范围

图论是一个非常庞大的分支。如果摊开看，遍历、连通分量、最短路径、最小生成树、拓扑排序、二分图、网络流，每一块都能写一本专项书。但训练营把图论拆成了好几个专题，专题1通常只做一件事：打地基。地基就是图怎么存、怎么把一个图完整地走一遍、怎么统计连通块。

为什么要把这些东西放在最前面？因为后面所有图算法都有一个共同前提：你得能按照某种规则把图中的顶点一个个访问过去。连遍历都写不熟，后面看最短路径、看并查集，代码也许看得懂，但一旦要修改判断逻辑、观察队列变化，立刻露馅。用一张表理清专题1常落的考点会比较直观：

这张表基本就是专题1的核心骨架，也解释了为什么我们会花不少篇幅讨论存储：结构没建对，后面全是隐形bug。

2. 邻接表还是邻接矩阵：选错存储结构会带来什么后果

2.1 两种存储结构各自的构造方式

邻接矩阵就是二维数组，用 edges[i][j] 记录 i 与 j 之间是否有边。构造门槛最低：读出a、b之后，无向图就写 edges[a][b]=edges[b][a]=1，有向图只写一条。访问任意一对顶点是否相邻，复杂度是 O(1)。这个结构简单，判断直接，但代价是空间。

邻接表则更像每个顶点背了一个背包，包里装着所有邻居。Python里最常见的写法是这样：

graph = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) # 无向图必须加反向边 graph[b].append(a)

这里有两个细节需要特别强调。第一，无向图必须双向登记，否则遍历时会漏掉一半路径。第二，顶点编号若从1开始，数组就开 n+1，让顶点编号可以直接当作下标使用，不会出现顶点编号恰好是n却越界的情况。

C++这边的建模也很标准：vector<vector<int>> graph(n + 1);，读入边后执行graph[a].push_back(b);，无向图再加一行graph[b].push_back(a);。Java则可以用ArrayList<Integer>[] graph，但要注意数组里的每个元素都要先初始化成new ArrayList<>()，这是一个非常容易漏的细节，漏了直接空指针。

2.2 稀疏与稠密：什么时候必须换方案

很多同学选存储结构全凭感觉，其实判断标准就一条：边数和点数的相对关系。如果边数接近O(V²)，比如N只有几百、M却有几万，邻接矩阵的空间可以接受。但邻接矩阵需要约N²个存储单元，N=5000时就到了2500万，用int存已经接近100MB，不少在线评测平台会直接报内存超限。反过来，邻接表只存实际存在的边，复杂度O(V+E)，在稀疏图下节省非常明显。

但邻接表也有自己的痛点：判断两个点是否直接相连，要顺着邻居列表找一遍。如果题目频繁要求判断是否存在某条边，邻接表最坏情况下会退化成O(E)，这时候邻接矩阵反而更合适。

一句话总结：除非题目明确是稠密小图，否则优先邻接表。机试和笔试题的默认场景基本都是稀疏图，邻接表应当是主选手。

3. DFS与BFS模板拆解：别背代码，背三件事

3.1 DFS：递归里只有三件事

DFS（深度优先）的代码在二叉树章节大家都写过，放到图里的时候，核心依旧只有三件事：标记当前点已访问、遍历邻居、对没访问过的邻居做同样的事情。差别在于，二叉树的递归天然不会回头访问父节点，而图的邻居往往是双向的，如果缺少visited数组，你会在两个相邻节点之间反复横跳，最终栈溢出。

visited = [False] * (n + 1) def dfs(node): visited[node] = True for nxt in graph[node]: if not visited[nxt]: dfs(nxt)

有个细节必须提醒：图遍历里的 visited 一旦标记，通常不需要在递归返回后撤销。它和回溯算法不同，回溯需要撤销状态以便尝试其他分支，而图的连通性访问要的是“我确实来过”，撤销反而会引发重复访问甚至无限递归。刚开始写图论题时，我经常把这两者混在一起，这是专题1最常见的思维误区。

如果担心递归栈溢出，可以把DFS改成手写栈。栈里存待访问节点，进栈时同样要标记visited。很多人在这里踩坑：弹出节点后才标记，会导致同一个节点被压入多次，遍历顺序也容易错乱。正确做法是压栈时立刻标记。

3.2 BFS：队列的一层含义

BFS广度优先的思路很直观：从起点出发，先处理直接相连的第一层邻居，再处理每个邻居的邻居。用队列实现，先进先出天然保证层序。

from collections import deque def bfs(start): q = deque([start]) visited[start] = True while q: node = q.popleft() for nxt in graph[node]: if not visited[nxt]: visited[nxt] = True q.append(nxt)

这段代码里最值得记住的一点是“入队即标记visited”。我第一次写BFS时习惯在出队时判断是否访问过，结果同一个节点被加入队列多次，小数据量下结果侥幸正确，遇到稠密图就变成灾难。入队时标记可以保证每个顶点最多只进队一次，队列长度被严格限制在顶点数量级别。

BFS还有一个天然优点：在无权图的场景里，队列天然按层排列，第一次到达某点的层数就是最短路径长度。如果需要记录距离，加一个dist数组就行，dist[start]=0，每个邻居首次被加入队列时执行 dist[nxt]=dist[node]+1。这正是下一个专题里最短路径问题的基础。

3.3 遍历顺序：递归、显式栈、队列三种写法输出差异

题目如果只要求输出从某点出发的所有可达顶点，三种写法得到的结果可能一致，也可能不一致，取决于你如何处理邻居顺序。一个非常实用的经验：如果题目对访问顺序有字典序要求，邻接表构建完成后先对 graph[i] 排序再遍历。

递归DFS天然输出深度优先序；手写栈则需要特别注意，栈是后进先出，邻居压栈顺序与输出顺序相反。比如想按1、2、3的邻居顺序访问，压栈时要反过来按3、2、1压入。BFS则按队列先进先出，通常与原顺序一致。

这些细节在刷题时很快会碰到：一道要求输出“字典序最小的DFS访问序列”的题，不少人用迭代栈被卡半天，就是因为栈的逆序这个反直觉特性。遇到这类情况，不要硬猜，先按序列推导一遍入栈出栈过程，问题往往瞬间清晰。

4. 专题1里高频翻车的四个细节

4.1 visited标记时机：不是所有时点都安全

第一个翻车点是visited标记时机。常见写法有两种，初学者容易写出下面这种：

from collections import deque def bfs_wrong(start): q = deque([start]) while q: node = q.popleft() if visited[node]: continue visited[node] = True for nxt in graph[node]: if not visited[nxt]: q.append(nxt)

这种写法在出队时才标记，从逻辑上不会死循环，但一个节点可能在 visited=False 时被多个邻居同时压入队列，虽然第二次出队时会被跳过，却会带来大量无意义的重复节点和额外耗时。小数据下能通过，大数据极可能超时。

DFS同样存在标记时点问题。递归函数入口标记是否一定安全？安全，但前提是数组长度正确。如果顶点编号从1到N，visited 大小应该设为N+1，直接使用 visited[node] 才不会越界。不要为了省内存把数组设为N，然后写出 visited[node-1] 这种下标翻译，一旦漏掉-1，越界错误非常难排查。

4.2 自环、重边与孤立点的处理

图论题读入边时，偶尔会出现a和b相同的情况，也就是自环。无向图自环表现为自己有一条指向自己的边，在邻接表里 graph[a] 会包含a。DFS遍历时，若 visited[a] 已为True，直接跳过，不影响正确性。但注意连通分量统计时，自环不会让孤立点变成连通块，它自己仍然算一个块。

重边则是同一条边输入了多次。邻接表会重复存储，遍历时会重复扫描，好在visited保证不会重复访问，多数题目不影响结果。不过在对边数敏感或需要去重的题目里，必须考虑用集合存储邻居，比如Python里的set，或者读入时判断是否已存在。

孤立点是最容易被忽视的点。统计连通分量时，外层循环必须遍历全部顶点：

count = 0 for i in range(1, n + 1): if not visited[i]: count += 1 dfs(i) # 或 bfs(i)

如果只从某个起点出发做一次遍历，孤立点永远无法被覆盖，连通块数量必然算错。这个错误我在训练营第一天就犯过，当时样例里恰好没有孤立点，一提交就露馅。

4.3 栈溢出、递归深度与评测环境

Python递归默认深度在1000左右，而机试题目顶点数N经常给到10^5甚至更多。这时递归DFS即使逻辑正确，也会直接报递归深度错误。可选方案有几个：

• 增大递归深度限制：sys.setrecursionlimit(1000000)，但只是放宽限制，极端数据照样可能爆栈。
• 改写成手写栈的迭代DFS，完全绕开递归深度限制。
• 用BFS代替DFS，只要题意不要求深度优先输出，BFS通常更稳。

顺带提一句，显式栈的DFS如果不小心把visited标记放错时机，可能造成的不只是性能下降，而是遍历结果失真。原因是某些路径会在尚未访问时被多次压栈，最终访问顺序偏离预期。出现这类问题时，建议边调试边打印栈内容，通常能快速定位。

4.4 输入顺序与输出顺序：一道题暴露的调试陷阱

有一次训练营的练习题是这样设计的（实际名称这里做替换，就叫模拟项目X吧）：输入N个点和M条无向边，每条边按输入顺序给出，要求输出从起点s出发的BFS访问顺序。我写完代码后本地样例全过，提交却一直报访问顺序与期望不一致。

后来把graph打印出来才发现问题。输入中第一条边是(2,1)，无向图会同时登记graph[1]里的2和graph[2]里的1；如果后续边又在graph[1]里加了3，那么graph[1]的邻居顺序是[2,3]。但题目评测时是按顶点编号维护邻接表的，期望顺序可能是[2,3]也有可能是[3,2]，完全取决于输入顺序，这就产生错位。

解决方案很简单：读入全部边之后，统一对每个 graph[i] 排序。很多题目默认期望这种结果，因为顺序可控。这类顺序问题在树形结构题里几乎不会遇到，但图是“邻居无序”的结构，排序有时就成了必要动作。

5. 一个综合练习：连通块统计与起点遍历全流程

5.1 题目需求与建图过程

为了把上面的问题串起来，用一道虚拟练习复盘完整流程（这是我练手时的关键版本，细节不影响复现）。题目描述：给定N个顶点和M条无向边，顶点编号从1到N，要求：

1. 输出图中连通块的个数；
2. 从起点s出发，输出DFS深度优先访问序列，邻居按顶点编号升序访问；
3. 从起点s出发，输出BFS广度优先访问序列。

读入方式模拟常规在线评测：第一行是N M s，接下来M行每行两个整数表示一条边。建图代码如下：

n, m, s = map(int, input().split()) graph = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().split()) graph[a].append(b) graph[b].append(a) for i in range(1, n + 1): graph[i].sort()

为什么排序放在建图之后？因为一次排序就够了，图形结构本身不因输入顺序改变。排序后DFS和BFS的邻居访问顺序统一按编号升序，输出就不会因为边的输入顺序出现玄学差异。

5.2 完整实现与输出分析

DFS部分用递归：

visited = [False] * (n + 1) order_dfs = [] def dfs(node): visited[node] = True order_dfs.append(node) for nxt in graph[node]: if not visited[nxt]: dfs(nxt) dfs(s)

BFS部分：

from collections import deque visited_bfs = [False] * (n + 1) order_bfs = [] q = deque([s]) visited_bfs[s] = True while q: node = q.popleft() order_bfs.append(node) for nxt in graph[node]: if not visited_bfs[nxt]: visited_bfs[nxt] = True q.append(nxt)

假设输入N=6、M=5、s=1，边分别是(1,2)、(3,2)、(4,5)、(5,6)、(1,4)，那么建完图并排序后各顶点邻居如下：graph[1]=[2,4]，graph[2]=[1,3]，graph[3]=[2]，graph[4]=[1,5]，graph[5]=[4,6]，graph[6]=[5]。

从1出发DFS会沿着1->2->3，然后回到1再走到4->5->6，输出顺序是[1,2,3,4,5,6]。BFS则先处理1的邻居2和4，再处理2的邻居3，再处理4的邻居5，最后到6，输出顺序是[1,2,4,3,5,6]。两种序列的差异一眼就能看出来，建议自己也推一遍。

连通块的统计还需要补一个对所有顶点的大循环。遍历到1时DFS会把[1,2,3,4,5,6]全部标记，count记1；接着i=4、5、6都已被标记，循环结束，答案是1个连通块。如果存在孤立点，每次遇到未访问点count加一即可。

5.3 复杂度与常见变体

上述实现的时空复杂度都是O(N+M)，因为每个顶点最多访问一次，每条边在遍历中最多被扫描两次（无向图每条边对应两个方向的邻居记录）。这是图论专题1里必须养成的习惯：写算法前先估算N和M的上限。如果N是10^5、M是2*10^5，O(N+M)完全安全。

变体也很常见。有的题目要求输出每个连通分量内部的顶点集合，可以在外层for循环里先记录一个临时数组，再统一输出。有的要求判断两个指定点a、b是否连通，一次从a出发的BFS或DFS后检查 visited[b] 即可。还有的题改成了有向图，代码几乎不变，只是建图时只写 graph[a].append(b)，遍历时不会反向误闯。

6. 从day48往后看：专题2之前先练熟这几件事

6.1 专题1的边界在哪里，专题2会突然跳到什么

按照常见训练营推进节奏，图论专题1覆盖到图的存储和两种遍历，基本就可以告一段落。接下来大概率会进入两类方向：一类是更高效的连通性处理，比如并查集；另一类是基于遍历的扩展应用，比如二分图判定、拓扑排序、最短路径里的BFS变体。

并查集和DFS/BFS解决连通性的思路差异值得提前体会。DFS/BFS会真正把图“走一遍”，时间复杂度O(N+M)，空间上需要建图存储。而并查集不建图，靠记录每个元素的父亲完成动态合并和查询，代码往往更短，但在需要输出路径的场景里不如遍历直观。

拓扑排序则是BFS思想在DAG（有向无环图）上的延展。入度为0的节点先入队，每处理一个节点，就把它指向的后继节点入度减1。专题1里BFS的“队列+visited”逻辑练熟了，拓扑排序的代码理解起来会非常顺滑。

6.2 三个能持续用很久的实战习惯

第一，不管什么图论题，建完图先打印一次邻接表。不要觉得浪费时间，邻接表一旦错了，后面所有代码都白写。打印一行并不会拖慢解题，却能避免一整晚的盲目调试。

第二，写BFS前先明确顶点上限，把visited数组初始化成n+1。写递归DFS前，专门想一下递归深度问题，别等爆栈了再回头改。如果题目顶点规模达到十万级，直接用迭代DFS或BFS，不要在递归深度上赌运气。

第三，题目对输出顺序有要求时，把“邻居排序”这个动作固化到模板里。只需一行代码，却能从根上排除一类玄学错误。我在训练营里见过太多人卡在输出顺序不匹配上，最后排查半天，原因就是邻居没有按编号排序。

当天打卡结束后，我又把邻接表打印出来，对着题目手动推导了一遍访问顺序。那种从“代码能跑”到“每一步都说得清为什么”的转变，才是这个专题真正该有的收获。图论的路还长，但地基打牢了，后面的事情都会顺很多。