看标题就知道今天要聊的是图遍历里的一个经典问题。很多刚学图的同学会默认一件事图的遍历就是从一个顶点出发把整个图走一遍。这个默认在连通图里成立但一旦图不是连通的只从一个点出发深度优先遍历也好广度优先遍历也好统统只能覆盖起点所在的“那一坨”顶点。剩下那些跟起点没有路径相连的顶点你永远碰不到。这正是“非连通图遍历”这个说法值得单独拎出来聊的原因。今天我就把这两件事掰开揉碎DFS和BFS各自的行走逻辑以及怎么在连通或非连通图上做一次完整的遍历。读完你不仅能写出对应代码还能顺手统计出图里有多少个连通分量——这在刷题和实际工程里都非常常用。1. 先把概念盘清楚连通图、非连通图与“一次遍历”的边界先别急着写代码。图遍历的问题九成是概念没理清导致的。很多代码写错不是循环写错了而是“图到底长什么样”没想明白。1.1 连通图、连通分量这些术语别搞混连通图的定义其实很朴素在一个无向图里任意两个顶点之间都存在一条路径。这里的路径是指沿着边走可以经过其他顶点。你可以从任何一个顶点出发一步一步走到任何一个其他顶点。举个生活里的例子假设你朋友圈里所有人都通过某种“共同好友”关系相互认识那这个关系网就是一张连通图。注意“连通”不等于“完全”。完全图要求任意两点直接相连而连通图只要求“走得通”。你在连通图里从A到B可能要绕几个中间人但一定能到。连通分量这个术语也容易搞混。它指的是在一个图里满足“内部任意两点连通”的极大顶点子集再加上它们之间的边。什么叫极大就是如果你再把任何一个外面的顶点加进来这个子图就不再连通了。连通分量就是图中一个个“独立王国”王国内部四通八达王国之间没有任何桥梁。对一张连通图来说它的连通分量只有一个——就是它自己。对非连通图来说它会被拆成好几个互不相连的连通分量。1.2 非连通图的真实结构块与块之间没有桥非连通图就是存在至少一对顶点它们之间没有任何路径。从任意一个顶点出发再怎么沿着边走都到不了某些顶点。直观看图的话非连通图就像几座彼此不相连的岛屿。每座岛内部是连通的岛与岛之间没有桥也没有船。这里要特别提醒一个容易忽略的点孤立顶点也算一个连通分量。一个顶点一条边都没有它自己内部是“连通”的因为它到自己当然有长度为0的路径。很多人在数连通分量时把孤立顶点漏掉这在对拍和调试时非常致命。所以非连通图可以理解成k个连通分量拼在一起彼此之间没有任何边。整张图看起来像一盘散沙但每个沙团内部是紧密的。1.3 一次遍历的“射程”起点决定了你能去哪图遍历的本质是“沿着边移动”每次执行DFS或BFS都有一个起点而这个起点决定了这次遍历的射程。如果你从某个顶点v出发执行一次深度优先或广度优先遍历那么你能访问到的顶点恰好就是v所在的那个连通分量里的所有顶点。分量内部的顶点一个都不会漏分量外部的顶点一个都碰不到。这不是实现细节而是由“遍历必须沿边走”这个本质决定的。举个例子图有6个顶点边是(0,1),(1,2),(3,4)顶点5是孤立的。那么从顶点2出发DFS只能访问0、1、2。从顶点3出发只能访问3和4。从顶点5出发只能访问5。想访问全部6个顶点就必须启动至少三次遍历。这个例子很粗糙但已经把核心矛盾摆出来了DFS和BFS是“单源”的一次执行只解决一个连通分量的问题。接下来我们看看这两种遍历内部到底怎么运作。2. DFS和BFS各自是怎么“走”的栈、队列与visited数组的分工理解了“一次遍历只能管一个分量”之后我们再往深处一层看看DFS和BFS各自怎么走。两者的核心区别就八个字一个纵深一个扩散。2.1 深度优先遍历不撞南墙不回头深度优先遍历的思想用一句话概括不撞南墙不回头。从起点出发选一条边往下走每到一个新顶点就继续往下探直到当前顶点的所有邻居都访问过了才退回上一个顶点换一条没走过的边继续走。你走迷宫的时候如果一路摸墙走进了一条死胡同就退回来换个岔路口这就是深度优先的走法。它的特点是优先追求“深入”而不是“铺开”。实现上DFS借助的是栈这种后进先出的结构。用递归写的时候函数调用栈天然就是那个栈所以代码特别短def dfs(graph, v, visited): visited[v] True print(v) for w in graph[v]: if not visited[w]: dfs(graph, w, visited)逻辑很直接进入顶点v把它标记为已访问然后遍历所有邻居w。只要w没访问过就递归进入w。因为递归栈会把“当前路径”完整保存所以能一路走到黑再一层层退回来。这里要补一个很多人忽略的点DFS的路径依赖顺序。如果你把邻居列表的顺序改一下遍历顺序会变但“能不能访问到某个顶点”这个结果不会变。所以复杂度分析、正确性证明都不依赖邻居顺序写代码时也别纠结先放哪个邻居。2.2 广度优先遍历波纹式一层层扩散广度优先遍历不一样。它不追求深入而是从起点开始一圈一圈往外扩散像把一块石头扔进平静的湖面波纹层层推开。BFS用队列实现先进先出。从起点开始先访问起点自己接着把起点的所有邻居全部入队。然后从队头取出一个顶点访问它再把它尚未访问的邻居全部入队。整个过程里先入队的顶点先被处理所以距离起点越近的顶点越早被访问。from collections import deque def bfs(graph, start, visited): q deque([start]) visited[start] True while q: v q.popleft() print(v) for w in graph[v]: if not visited[w]: visited[w] True q.append(w)注意一个细节BFS里在把邻居w入队的时候就标记visited而不是等w出队再标记。这个细节很重要后面我专门用一小节说。如果你在出队时才标记同一个顶点可能被多个邻居重复入队队列里会出现大量重复元素代码虽然可能“碰巧对”但复杂度和日志都会很难看。BFS最有价值的特性是在无权图中它天然能找出从起点到每个顶点的最短路径。因为所有邻居都是同一层先访问到的路径一定是最短的。这也是为什么网格最短路、最少步数问题基本都无脑选BFS。2.3 visited数组防止死循环的那个关键开关图里经常有环比如A连着BB连着CC又连着A。如果没有visited数组DFS会在A、B、C之间反复横跳永远停不下来BFS会让同一个顶点不断入队。所以visited数组是遍历的命门。visited数组的作用就是记录“这个顶点是否已经被访问过”。每次要访问一个顶点之前先查visited访问之后立刻把它标成True。这样可以保证每个顶点最多被访问一次遍历必终止。我见过不少初学者问图是树的时候能不能不写visited树没有环从根出发往下走确实不会重复访问同一个顶点所以理论上可以不写。但问题是一旦图里有环或者你处理的是无向图没有visited的后果就是灾难性的。所以统一习惯不管有没有环一律用visited。这个习惯能让你的代码在边界情况下一分钱都不用修。3. 从“一次遍历”到“遍历全图”外层循环补上缺的那一环现在回到最初的问题DFS和BFS如何实现对非连通图的遍历答案就三个字外层循环。3.1 标准套路外层循环 全局visited 单源遍历思路非常简单准备一个全局共享的visited数组长度为顶点数。从顶点0开始依次检查每个顶点。如果某个顶点还没被访问过说明它属于一个新的连通分量。以它为起点执行一次DFS或BFS。这次遍历会把该顶点所在整个连通分量里的所有顶点全部标记成已访问。继续往后找下一个未访问的顶点。这个套路的关键是visited数组必须在所有遍历之间共享不能每次启动DFS/BFS时重新初始化。一旦重新初始化你想用前面的遍历结果来避免重复启动就完全失效了。3.2 代码落地完整遍历与连通分量计数直接给一份完整可跑的模板。先来个DFS版本def dfs_component(graph, v, visited): visited[v] True for w in graph[v]: if not visited[w]: dfs_component(graph, w, visited) def traverse_all_dfs(graph, n): visited [False] * n component_count 0 for v in range(n): if not visited[v]: component_count 1 dfs_component(graph, v, visited) return component_countBFS版本也一样只需要把里面的单源遍历函数替换成bfs_componentdef bfs_component(graph, start, visited): q deque([start]) visited[start] True while q: v q.popleft() for w in graph[v]: if not visited[w]: visited[w] True q.append(w) def traverse_all_bfs(graph, n): visited [False] * n component_count 0 for v in range(n): if not visited[v]: component_count 1 bfs_component(graph, v, visited) return component_count这个component_count就是连通分量个数。每次外层循环里检测到未访问顶点说明一个新分量开始了计数器加一然后调用单源遍历把整个分量染完。因为一次遍历会覆盖分量内所有顶点所以同一个分量绝不会被计数器数两次。3.3 为什么这套写法在连通图上也不会出问题有人可能会问如果图本身是连通的这个外层循环是不是白写了不会白写也不会出错。连通图只有一个连通分量。外层循环从顶点0开始第一次发现visited[7]是False启动一次DFS后整个图所有顶点都会被标记成True。之后循环继续检查顶点1、2、3……它们全是True一个都不会再触发新的遍历。最终component_count等于1完全正确。可以说“连通图的整体遍历”只是“非连通图遍历”的一个特例。另外这套模板还有一个很实用的副产品——判断图是否连通。你只需要跑一次从顶点0出发的单源遍历然后检查visited数组里有没有False。如果全是True图连通如果存在False图不连通。这个操作在解题时经常用来快速排除一些不可能的情况。还有一个隐藏知识点值得提一下一次完整的DFS/BFS全图遍历会把图的边集合切成若干棵“遍历树”合在一起就是“遍历森林”。无向图中如果有V个顶点、k个连通分量那么遍历森林里的树边总数是V - k。每个分量内部有“顶点数减一”条树边加起来正好是V - k。这个结论在证明和复杂度推导里偶尔会用到。4. 邻接表、邻接矩阵与递归/迭代四种实现的复杂度对比图遍历的代码写到这一步接下来要考虑的是图本身怎么存代码用递归还是迭代这两个选择直接影响性能和写法值得单独开一章说清楚。4.1 存储结构先选对邻接表与邻接矩阵的取舍邻接表的思路很直接每个顶点一个列表列表里存它直接相连的邻居。无向图中每条边会出现在两个顶点的列表里所以总共存2E个元素E是边数。邻接矩阵则是一个V行V列的二维数组。matrix[v][w]为1表示v和w之间有边为0表示没有。无向图的矩阵是对称矩阵有向图则不一定。选哪个我的建议很明确除非顶点数特别小比如几十个以内或者输入本身就是矩阵否则优先用邻接表。邻接表按需遍历邻居稀疏图下省空间也省时间。邻接矩阵虽然判断“两个顶点是否直接相连”是O(1)的但遍历一个顶点的所有邻居时必须傻乎乎地把一整行都扫一遍哪怕这一行里只有两三个1。4.2 复杂度计算O(VE) 与 O(V^2) 是怎么来的很多文章直接丢出一个复杂度结论但不解释来源。这里我把计算过程摊开说。邻接表 DFS或BFS每个顶点只会被访问一次遍历邻居的循环也只会针对每个顶点执行一次。无向图里每条边出现在两个顶点的邻接表里所以所有循环加起来会检查约2E个邻居。总时间 顶点访问O(V) 邻居扫描O(E) O(V E)。邻接矩阵 DFS或BFS访问每个顶点时为了找它的邻居必须扫描一整行长度为V。每个顶点访问一次所以总扫描次数 V * V O(V^2)。哪怕图里一条边都没有矩阵也要求你扫完所有格子。这就是O(V^2)的真正来源。空间复杂度也要配套说。邻接表是O(V E)邻接矩阵是O(V^2)。再加上两个遍历都要用的visited数组O(V)以及递归时系统栈或显式队列最大O(V)。所以总空间分别对应O(VE)和O(V^2)。如果你拿一张10000个顶点、20000条边的稀疏图测试邻接表遍历大概几毫秒邻接矩阵光初始化就要扫一亿个格子差距非常直观。4.3 迭代版DFS递归之外的另一个选择递归DFS虽然短但遇到特别深的图比如一条长链会爆栈。这时候可以显式维护一个栈手动模拟递归def dfs_iter(graph, start, visited): stack [start] while stack: v stack.pop() if visited[v]: continue visited[v] True print(v) for w in graph[v]: if not visited[w]: stack.append(w)这个版本有几个细节要注意因为使用的是出栈时标记同一个顶点可能被多个邻居压进栈所以弹出后要再次检查visited否则会重复处理。邻居入栈的顺序会影响遍历顺序。如果你希望和递归版完全一致入栈时需要把邻居列表倒序遍历。迭代版不需要系统递归栈也不受递归深度限制在深度很大的树上更稳。相比之下BFS本身就是用队列迭代写的天然没有递归深度问题。我把几种组合的复杂度整理成一张表方便收藏备查存储结构遍历算法时间空间适用场景邻接表DFS迭代O(VE)O(VE)深度大的图防爆栈邻接表DFS递归O(VE)O(VE)深度可控、代码简洁时用邻接表BFSO(VE)O(VE)无权图最短路、层级扩散邻接矩阵DFS/BFSO(V^2)O(V^2)顶点少或稠密图、频繁查两点是否相连5. 别只会背代码这些场景真的用得上非连通图遍历学会了模板最怕的是只会背代码、不知道怎么用。我挑三个特别典型的场景让你直观感受“非连通图遍历”在真实问题里的价值。5.1 二维网格里的“岛屿数量”不建图的图遍历有一道非常经典的题给一个二维网格里面是0和11代表陆地0代表水。上下左右相邻的1算同一个岛屿求岛屿数量。把格子看成顶点相邻的1之间看成有一条边那么“求岛屿数量”本质上就是求这张隐含图的连通分量个数。关键在于你不需要真的去建邻接表或邻接矩阵直接在网格上做遍历就行。def num_islands(grid): if not grid: return 0 rows, cols len(grid), len(grid[0]) visited [[False] * cols for _ in range(rows)] def dfs(r, c): visited[r][c] True for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc r dr, c dc if 0 nr rows and 0 nc cols \ and grid[nr][nc] 1 and not visited[nr][nc]: dfs(nr, nc) count 0 for r in range(rows): for c in range(cols): if grid[r][c] 1 and not visited[r][c]: count 1 dfs(r, c) return count这里最妙的点是外层循环扫描所有格子遇到没访问过的1就启动一次DFS把整座岛都标记掉。这和我们前面说的“外层循环 全局visited”是同一个套路只是图的载体从邻接表变成了网格坐标。如果你刚看完前面几章可以直观感受到这个双层循环扫描就是“遍历非连通图”的另一种形态。网格里可能有几十个岛屿每次DFS只处理其中一座。5.2 社交网络连通块、可达性分析与系统巡检实际业务里“求一个网络里有多少个互不相连的群组”几乎是连通分量检测的标准应用。拿社交网络举例用户是顶点关注关系是边。如果平台想分析“有多少个彼此不交流的圈子”就可以把所有用户放到图里执行一次完整遍历统计连通分量数。每个分量就是一个独立社群运营可以针对不同社群做差异化策略。这种分析不需要你额外设计算法前面那段traverse_all_dfs直接搬过来就能用。另一个场景是可达性分析。比如一个系统里有若干个“入口”你想知道从这些入口能访问到哪些资源。这种问题本质是“多源可达”你只需要把所有入口都标记为已访问然后执行一次遍历就能得到所有能触达的资源。反过来如果你想找出“哪些资源谁都无法触达”可以分两次遍历第一次从所有入口出发做单源遍历把可达的标记第二次扫描所有顶点那些仍然没被访问的就是完全孤立的资源块。这类全图覆盖的思想在工作中比想象中常见得多服务依赖分析、故障影响面排查、权限访问边界梳理底层都是图遍历。所以别看“图的遍历”好像是数据结构第一章的内容它的迁移能力非常强。5.3 有向图带来的新变化弱连通与强连通分量以上讨论默认是无向图。有向图会带来一些新问题。有向图里边是有方向的。从A能走到B不代表从B能走回A。所以“连通”的概念也要做区分。无向图的“连通分量”在有向图里要换成两个不同的概念弱连通分量把有向边全部忽略方向当成无向边看得到的连通块。强连通分量分量内任意两个顶点之间都存在双向可达路径。普通一次DFS在有向图里能覆盖的范围是从起点沿箭头方向能到达的所有顶点。比如A和B之间有A到B的边但B到A没有边从A出发就能访问B从B出发却访问不到A。如果你想完整遍历一张有向图的所有顶点依然可以用“外层循环 visited”的模板每次从新起点出发做单源遍历。但要注意的是这种遍历得到的结果和“强连通分量划分”并不等价。真正找强连通分量要用更专门的算法比如大家常说的Tarjan或Kosaraju不过这两个算法都建立在“能一趟DFS把图走完”的基础上。把本文的基础打牢后面接触那些进阶算法会轻松很多。6. 实操中容易踩的坑与调试技巧最后说点实际跑代码时才会遇到的问题。很多代码纸上看很完美一跑就出事而且出错的位置往往不在算法逻辑而在一些不起眼的细节。6.1 递归深度很长的链会悄悄击穿调用栈递归版DFS写起来爽但它有一个隐形的敌人——递归深度。如果图的某个连通分量是一条很长的链比如5000个顶点串成一条直线递归版DFS会一路往下递归5000层。很多语言的调用栈有上限一旦超过就抛出栈溢出或递归深度错误。你看到报错的第一反应可能是“算法写错了”其实算法没问题是递归栈被击穿了。遇到深度不确定的图我有两个建议优先用迭代版DFS或BFS显式栈/队列不受调用栈深度限制。如果必须用递归且知道深度可控可以适当提高递归限制但别把上限调到天上因为每个递归帧都吃内存硬调大只是延缓问题。在图的题里一条链的输入非常常见。所以我现在写DFS时如果没有特别说明默认用迭代栈版本省心。6.2 visited的标记时机入队标记还是出队标记这是初学者最容易踩的坑我单独拎出来强调。BFS的正确写法是在顶点入队时标记visited而不是等它出队时再标记。原因很简单如果出队才标记当顶点A和B都能访问到公共邻居C时C可能会被A入队又会被B入队队列里出现两份C。虽然最终结果可能还是对的但效率变差而且如果你在图上打印遍历顺序会发现某些顶点被重复输出。迭代版DFS也有类似的坑。如果你用出栈时标记就必须在弹出后先检查visited否则同一个顶点会被多次压栈、多次处理。稳妥的规则是这样BFS入队时标visited。递归DFS进入函数第一行就标记。迭代DFS出栈后标记但入栈前也要检查一次。这三条规则记熟能避免一大堆莫名其妙的重复访问问题。6.3 调试模板用一张6顶点小图跑通全流程如果你写了代码但不确定对不对自己手动构造一张小图边数少、分量清晰是最快的验证方式。我建议的调试图就是这样6个顶点边是(0,1),(1,2),(3,4)顶点5孤立。期望结果是连通分量数3。跑代码时打印出每个新启动的起点你最好能看到类似这样的输出起点0、起点3、起点5之后visited数组应该全是True。一个判断连通性的小工具函数也值得写进笔记def is_connected(graph, n): visited [False] * n dfs_component(graph, 0, visited) return all(visited)从顶点0出发跑一次遍历如果visited全True说明全图从一个点就能走完——连通图。这个函数在任何刷题场景里都能作为辅助工具直接复用。我在实际写这类代码时最常用的模板就是外层循环 visited 单源遍历。三个部分各司其职外层循环负责找到还没被染色的顶点visited负责全局染色单源遍历负责把一个连通分量完整染完。这套模板不只在刷题里好用在真实需求里遇到“全图划分”的问题我第一时间想的也是它。最后再分享一个我自己养成的习惯每写完一次遍历先拿连通图和非连通图各测一遍。连通图验证“一次遍历能全覆盖”非连通图验证“外层循环能正确找全所有分量”。两遍都过了这题基本就稳了。希望这篇能帮你彻底摆脱“从顶点0出发DFS一下就完事”的思维惯性。