今天是代码随想录算法训练营的第五十三天题目回归到一个很基础但特别容易被忽视的问题寻找图中存在的路径。这道题按代码随想录的编排出现在图论章节的开头表面上只是问从点A到点B有没有路但背后牵出的是整个图论入门的核心动作怎么存储图、怎么遍历图、怎么用数据结构加速判断。别小看它我见过很多同学二叉树刷得飞起一碰到图就卡住恰恰是没把这道题吃透。这篇文章就把我这一天的完整思考、三种写法、以及踩过的几个坑全部梳理出来希望能给正在刷图论起步题的读者一点参考。1. 题目模型与存在性到底在问什么1.1 从输入输出看题目的真实面貌题目给定一个数 n 表示节点总数节点编号从 0 到 n-1再给一个二维数组 edges 表示图中的边每个元素比如 [u, v] 说明 u 和 v 之间有一条无向边。最后给出起点 start 和终点 dest有的版本叫 finish要求判断 start 和 dest 之间是否存在至少一条路径。如果存在返回 true否则返回 false。举个例子。n 3edges [[0,1],[1,2],[2,0]]start 0dest 2这个图其实就是个三角形0 可以透过 1 到 2或者透过 2 直接到 2所以答案是 true。如果 edges 改成 [[0,1]]start 0dest 2那 2 完全孤立答案就是 false。这个判断看起来简单但它要求我们能够在任意规模的图上快速确认两个点是否连通而不是一条一条路径去数。1.2 为什么说它比最短路径更基础很多人把这道题和最短路径搞混一看到路径两个字就想上 Dijkstra 或者 Floyd。其实这道题根本不关心路径有多长也不关心走几步只关心能不能到达。说的直白点最短路径问的是怎么走最近路径存在性问的是有没有路可走。这两者难度差距很大前者需要在所有可行路径中找最优后者只要找到一个可达路径就可以立刻停止。所以这道题真正想训练的是两个能力一是根据题目描述选择合适存储方式的能力二是判断一个问题适合用遍历还是用并查集的能力。后面所有图论题包括最小生成树、拓扑排序、连通分量都会把这两个能力作为底层基础。我刷到后面发现凡是卡住的地方往往不是算法没学过而是最开始的建模就错了。2. 记忆化DFS用递归把图走一遍2.1 邻接表是怎么来的DFS 的第一步是确定图怎么存。绝大多数情况下图论题不要用邻接矩阵因为 n 一旦到 10 的 5 次方邻接矩阵就会产生 10 的 10 次方个格子内存直接爆掉。更合理的做法是邻接表每个节点对应一个列表列表里装着它所有能直接到达的邻居。构建邻接表的代码非常固定几乎每道图论题都会用到值得背下来ListListInteger graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } for (int[] edge : edges) { graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); // 无向图必须双向添加 }这里最关键的注释就是无向图必须双向添加。2.2 递归函数的结构与visited的作用DFS 写起来很像二叉树的递归但比二叉树多了一个重要机制visited 标记。二叉树天然没有环从根往子节点走不会走回自己图不一样无向图中两个节点互相连比如 0 和 1 之间有一条边如果不做标记从 0 走到 1 后又从 1 走回 0就会无限循环直到系统栈爆掉。一个标准的 DFS 判断路径是否存在可以这样写boolean dfs(int node, int dest, boolean[] visited, ListListInteger graph) { if (node dest) return true; visited[node] true; for (int next : graph.get(node)) { if (!visited[next]) { if (dfs(next, dest, visited, graph)) { return true; } } } return false; }注意几个细节点。第一进入函数后第一步是判断当前节点是不是终点如果是直接返回 true不需要再做任何遍历。第二把当前节点标记为 visited 的时机是在循环之前而不是循环内部这样能防止同一个节点被重复进入。第三子节点递归返回 true 时当前递归立刻向上返回 true因为我们已经确定有路径了不需要再探索其他分支。2.3 一个隐蔽的错误盲目回溯很多刷过回溯题的同学看到这里有问为什么 DFS 后不恢复 visited在排列组合类题目里我们需要把标记清掉让同一个节点在另一条路径上可以再次使用但路径存在性问题只需要回答有没有一旦走到某个节点就说明这个节点已经被探索过了。如果恢复标记最坏情况下可能把本可以剪枝的部分重新展开导致大量重复计算。我一开始就是不小心用了回溯式写法每一层递归结束后把 visited 清回 false结果在一条长链图上跑了接近指数级的次数超时到怀疑人生。在这个题目里visited 的作用不是记录当前路径上是否经过而是记录从起点出发是否已经到达过要的就是一次性完成整个可达域的计算。想通了这一点DFS 就会顺畅很多。3. BFS与DFS的等价性换一种顺序避开系统栈3.1 为什么说BFS更让人安心DFS 用的递归开销由函数调用栈承担。当图特别大、链条特别深时比如一条 20 万个节点组成的直线DFS 递归深度也会达到 20 万层很多语言默认的栈大小根本承受不住会造成栈溢出或崩溃。BFS 改用显式队列不再占用系统调用栈所以在大规模输入下更稳妥。路径存在性不要求最短所以 BFS 和 DFS 在时间复杂度和最终结果上是一致的都是 O(NE)N 是节点数E 是边数。区别只在于遍历顺序DFS 优先往深处钻BFS 按层往外扩散。对于纯可达性判断两者没有本质优劣选哪个主要看你更熟悉哪套框架。3.2 BFS的代码骨架与入队细节下面这个 BFS 版本我推荐作为备选模板boolean bfs(int start, int dest, ListListInteger graph) { if (start dest) return true; boolean[] visited new boolean[graph.size()]; QueueInteger queue new LinkedList(); queue.offer(start); visited[start] true; while (!queue.isEmpty()) { int node queue.poll(); for (int next : graph.get(node)) { if (next dest) return true; if (!visited[next]) { visited[next] true; queue.offer(next); } } } return false; }这里有一个很多人忽略的细节在把 next 入队之前就要把 visited 标记设为 true而不是在出队的时候才标记。如果等出队再标记同一个节点可能被上一个节点入队一次又被另一个节点入队一次队列中会出现大量重复元素导致空间开销增大甚至在某些极端条件下死循环。这个教训我在做多源 BFS 时踩过很深放在路径存在性里也同样有效。3.3 两种遍历在实际表现上的差异从答案上看DFS 和 BFS 返回的都是布尔值没有区别。但如果题目改成给出任意一条可行路径DFS 会更自然因为递归栈天然保存了路径如果题目改成判断是否连通并给出层数BFS 更合适因为按层扩散天然能记录步数。这道题两者都能用我的建议是如果你对递归有信心DFS 代码更短如果你担心递归深度或者 n 的规模很大写 BFS 更省心。还有一种更省心的方案就是下面要说的并查集。4. 并查集为存在性量身定做的数据结构4.1 为什么存在性题可以不用遍历DFS 和 BFS 本质上都是从起点出发摸到终点就停的在线搜索。但如果题目问的不是单次查询而是多次查询比如给你一堆 (start, dest) 对让你分别判断是否连通DFS 每次都要重新遍历一遍图累计成本很高。并查集的做法完全不同先把所有边合并到集合里把整个图的连通关系一次性建立好之后任意两个点是否连通只需要看它们所属的集合是否相同。这就像判断两个陌生人是否存在社交关系链DFS 是顺着一个人的朋友列表去搜另一个人并查集则是先把所有人按关系分好组最后问你们俩是不是一组的。4.2 find与union的路径压缩实现并查集核心就两个操作查find和并union。查是找某节点所在集合的根节点并是把两个集合合并。为了让树尽量矮我们需要路径压缩在 find 的过程中把路上遇到的每个节点都直接挂到根节点上这样下次查询时几乎一步到位。按秩合并也是常见优化用 rank 记录树高把矮树挂到高树下避免极端退化。一个完整的板子我写在这儿class DSU { int[] parent; int[] rank; DSU(int n) { parent new int[n]; rank new int[n]; for (int i 0; i n; i) parent[i] i; } int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } void union(int x, int y) { int fx find(x); int fy find(y); if (fx fy) return; if (rank[fx] rank[fy]) { parent[fx] fy; } else if (rank[fx] rank[fy]) { parent[fy] fx; } else { parent[fy] fx; rank[fx]; } } boolean connected(int x, int y) { return find(x) find(y); } }调用逻辑很简单遍历 edges对每条边执行 union(edge[0], edge[1])全部合并后直接 return dsu.connected(start, dest)。不需要构建邻接表也不需要 visited代码量甚至比 BFS 还少。4.3 复杂度分析与适用边界并查集在配合路径压缩和按秩合并的情况下单次 find 操作的时间复杂度趋近于常数级别准确说是反阿克曼函数 α(N)在合理数据范围内可以认为就是 O(1)。整个预处理也就是遍历一次 edges复杂度 O(E·α(N))。比 DFS/BFS 的 O(NE) 更优尤其在多次查询场景下优势明显。但并查集也不是万能的。它擅长回答是否连通却不擅长回答怎么走也不适合输出具体路径。如果你想在判断连通之后进一步还原出一条可行路径还得靠 DFS。所以我一般先看题目问什么只要问是否存在并查集永远是第一候选如果题目额外要求输出任意路径或输出最短路径我才转回遍历法。5. 实战踩坑记录从超时到AC的一波三折5.1 第一版邻接矩阵直接内存超限我第一次做这道题时想都没想就用了二维数组存边因为当时觉得判断两点是否连通用邻接矩阵最直观。结果测试数据里 n 给到 10 的 5 次方邻接矩阵需要 n 的平方个布尔值哪怕每个布尔只占 1 字节也需要 10 GB 内存代码一提交就 MLE。后来老老实实换成邻接表DFS 一次就过了。这个教训让我养成了一个习惯凡是看到 n 超过 10 的 4 次方第一步就排除邻接矩阵。图论题的输入规模往往就是为邻接表设计的强行用矩阵解决不了任何算法问题只会把自己卡死。5.2 漏掉反向边导致的错误false第二个坑更隐蔽。题目明确说是无向图但我最开始构建邻接表时只在一条方向上加边比如 edges [[1,0]]我在 graph.get(1) 里加了 0却忘了在 graph.get(0) 里加 1。结果 start 0dest 1 时DFS 从 0 出发发现邻居列表为空立刻返回 false。测试数据如果恰好有一条边是从大编号指向小编号就会漏判。排查这种问题最有效的办法是用最小的自画像测试自己画三个节点、两条边手动推导一遍应该形成的邻接表然后打印出来核对。无向图的双向建边是最容易被忽略的基础操作但它直接决定答案的对错。5.3 起始点等于终点的边界情况还有一个边缘用例很多人没考虑到start 和 dest 恰好是同一个节点。按常识一个节点到自己当然存在路径长度为零的路径也算路径。所以正确做法是一开始就判断 if (start dest) return true。如果你不写这个判断DFS 或 BFS 也能处理因为访问 start 时发现 node dest照样返回 true但如果你用的是并查集connected 调用前也应当处理避免不必要的合并操作。虽然这道题不处理大概率也能过但边界情况在任何面试中都是加分项养成习惯没坏处。我还遇到过一种错误是 DFS 的 visited 标记放在递归结束之后才设置。比如我先判断终点然后把 visited 设置为 false再进去循环。这种写法会反复遍历同一个节点在环形图上导致死循环或者超时。排查了很久才发现是标记的位置放得不对。递归逻辑里每个语句的先后顺序都决定了算法能否终止尤其是 visited 这种具有记忆性质的数组位置错了整个语义就变了。6. 这道题在训练营里的位置与后续延伸6.1 为什么要安排在第53天看代码随想录的学习曲线会发现二叉树、回溯、贪心等专题都放在前面图论是比较晚才出现的模块。到了第五十三天其实已经具备了一定的递归基础和回溯功底这时候切入图论正好可以把之前学过的递归思维迁移过来。而寻找存在的路径作为图论的开胃菜难度设置也很合理它不需要你掌握复杂的图论定理只需要你会在图上做一次遍历或者会用最基础的并查集。从训练节奏来说这个位置还有一个好处在经过大量二叉树递归训练之后DFS 的写法对大部分人不再陌生转向图遍历时只需要多理解一个 visited 标记。如果这道题放在训练营早期很多同学可能连邻接表都建不明白反而会打击信心。6.2 后续题目的自然延伸把这道题吃透之后再去看省份数量、岛屿数量这类连通性问题会发现核心思路完全一致。省份数量本质上是判断哪些城市直接或间接相连可以用并查集合并也可以用 DFS 染色岛屿数量则是把二维网格当作图相邻的陆地构成连通块DFS 或 BFS 扫描一遍就行。它们都建立在遍历整个图、标记已访问节点的框架上。再往后最小生成树的 Kruskal 算法会用到并查集拓扑排序会用到邻接表和入度最短路会用到 BFS 和优先队列。可以说这道题里的两个工具——邻接表和并查集——会一路陪伴你到图论专题的最后一题。所以别因为题目简单就跳过把每行代码的意图都搞清楚后面能省下大把时间。6.3 我站在第五十三天回看的一点体会刷到图论这个节点我最大的感受是算法训练营的意义不在于把每道题的解法背下来而是逼着你不断切换思维模型。二叉树是一维递归模型回溯是带撤销的递归模型图论则是一个有环需要记忆化的递归模型。如果你只会照着二叉树模板写遇到 visited 就会懵如果你只学过并查集的模板遇到输出路径的变体就又不会了。所以每刷一道题我都会问自己这道题的独特难点到底在哪它逼我做出了哪些和之前不同的决定就拿寻找存在的路径来说它逼我决定用邻接表而不是邻接矩阵逼我理解为什么 visited 不需要回溯逼我意识到规模大的时候 BFS 比递归 DFS 更安全。这些决定单独拎出来都很小但它们连起来就是一个从会写代码到会设计算法的转变过程。最后分享一个我实测有效的小技巧做任何图论题之前先在草稿纸上把样例画成节点和边的图哪怕只是三五个节点也比直接盯着控制台输出更直观。画完图之后你自然能看清是应该从起点搜索还是应该用并查集合并所有边。这道题我后来用三种方法各写了一遍每一遍都会加深对图论基础模型的理解。如果你也刷到训练营第五十三天附近不妨把 DFS、BFS、并查集三种解法都实现一遍这种一题多解的训练比盲目刷新题有用得多。