企业官网建设流程全解析

今天是代码随想录算法训练营的第五十三天，题目回归到一个很基础但特别容易被忽视的问题：寻找图中存在的路径。这道题按代码随想录的编排出现在图论章节的开头，表面上只是问"从点A到点B有没有路"，但背后牵出的是整个图论入门的核心动作：怎么存储图、怎么遍历图、怎么用数据结构加速判断。别小看它，我见过很多同学二叉树刷得飞起，一碰到图就卡住，恰恰是没把这道题吃透。这篇文章就把我这一天的完整思考、三种写法、以及踩过的几个坑全部梳理出来，希望能给正在刷图论起步题的读者一点参考。

1. 题目模型与"存在性"到底在问什么

1.1 从输入输出看题目的真实面貌

题目给定一个数 n 表示节点总数，节点编号从 0 到 n-1，再给一个二维数组 edges 表示图中的边，每个元素比如 [u, v] 说明 u 和 v 之间有一条无向边。最后给出起点 start 和终点 dest（有的版本叫 finish），要求判断 start 和 dest 之间是否存在至少一条路径。如果存在返回 true，否则返回 false。

举个例子。n = 3，edges = [[0,1],[1,2],[2,0]]，start = 0，dest = 2，这个图其实就是个三角形，0 可以透过 1 到 2，或者透过 2 直接到 2，所以答案是 true。如果 edges 改成 [[0,1]]，start = 0，dest = 2，那 2 完全孤立，答案就是 false。这个判断看起来简单，但它要求我们能够在任意规模的图上，快速确认两个点是否连通，而不是一条一条路径去数。

1.2 为什么说它比"最短路径"更基础

很多人把这道题和最短路径搞混，一看到"路径"两个字就想上 Dijkstra 或者 Floyd。其实这道题根本不关心路径有多长，也不关心走几步，只关心"能不能到达"。说的直白点，最短路径问的是"怎么走最近"，路径存在性问的是"有没有路可走"。这两者难度差距很大：前者需要在所有可行路径中找最优，后者只要找到一个可达路径就可以立刻停止。

所以这道题真正想训练的是两个能力：一是根据题目描述选择合适存储方式的能力，二是判断一个问题适合用遍历还是用并查集的能力。后面所有图论题，包括最小生成树、拓扑排序、连通分量，都会把这两个能力作为底层基础。我刷到后面发现，凡是卡住的地方，往往不是算法没学过，而是最开始的建模就错了。

2. 记忆化DFS：用递归把图"走一遍"

2.1 邻接表是怎么来的

DFS 的第一步是确定图怎么存。绝大多数情况下，图论题不要用邻接矩阵，因为 n 一旦到 10 的 5 次方，邻接矩阵就会产生 10 的 10 次方个格子，内存直接爆掉。更合理的做法是邻接表：每个节点对应一个列表，列表里装着它所有能直接到达的邻居。

构建邻接表的代码非常固定，几乎每道图论题都会用到，值得背下来：

List<List<Integer>> 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, List<List<Integer>> 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(N+E)，N 是节点数，E 是边数。区别只在于遍历顺序：DFS 优先往深处钻，BFS 按层往外扩散。对于纯可达性判断，两者没有本质优劣，选哪个主要看你更熟悉哪套框架。

3.2 BFS的代码骨架与入队细节

下面这个 BFS 版本我推荐作为备选模板：

boolean bfs(int start, int dest, List<List<Integer>> graph) { if (start == dest) return true; boolean[] visited = new boolean[graph.size()]; Queue<Integer> 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(N+E) 更优，尤其在多次查询场景下优势明显。

但并查集也不是万能的。它擅长回答"是否连通"，却不擅长回答"怎么走"，也不适合输出具体路径。如果你想在判断连通之后进一步还原出一条可行路径，还得靠 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 = 0，dest = 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、并查集三种解法都实现一遍，这种一题多解的训练，比盲目刷新题有用得多。