跳到主要内容

LeetCode 1971. 寻找图中是否存在路径

本节目标

把无向边转为邻接表，从 source 迭代 DFS 搜索 destination。

这是图的表示与遍历中最基础的显式无向图可达性问题：边给出后先建立邻接表，再从 source 扩张搜索范围。

查看 LeetCode 原题

题意与约束​

有 n 个编号为 0 到 n - 1 的顶点，每条边 [u, v] 表示双向通行。判断是否存在从 source 到 destination 的路径。图可能不连通且可能有环；当 source 与 destination 相同时，长度为零的路径已经成立。

直接思路与瓶颈​

可以反复扫描整个边集：每找到一条一端已达、另一端未达的边，就把另一端加入可达集合。最坏情况下每扩张一个顶点都要重扫 E 条边，复杂度会达到 O(VE)。

图模型与算法推导​

先为每个顶点建立邻接表，之后枚举一个顶点可走向哪里只需遍历它的实际邻居。把 source 入栈并立即标记；每次弹出一个顶点，若它就是 destination 则返回真，否则把尚未访问的邻居标记并压栈。栈为空仍未命中目标，说明 destination 不在 source 所在连通分量。

正确性依据​

不变量是：栈中的每个顶点都已从 source 可达，且 visited 中的顶点都已经入栈或处理过。初始化时 source 满足；处理一个顶点后，任何新压入的邻居都通过一条边与可达顶点相连，因此仍可达。图中每个可达顶点最终都会沿某条已处理边被发现，所以命中 destination 当且仅当存在路径。

样例执行过程​

取 n = 6，边为 [[0,1],[0,2],[2,3],[3,4]]，查询 source = 0 到 destination = 4。建表后 graph[0] = [1,2]。初始 stack = [0]、visited = {0}；弹出 0 后依次发现 1、2，栈为 [1,2]、visited = {0,1,2}。弹出 2 后发现 3，栈为 [1,3]；弹出 3 后发现 4，栈为 [1,4]。下一次弹出 4 即命中目标，返回 true；孤立的顶点 5 从未入栈，不影响结论。

代码实现​

C++17
#include <vector>

using namespace std;

class Solution {
public:
    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n);
        for (const auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }

        vector<bool> visited(n, false);
        vector<int> stack{source};
        visited[source] = true;
        while (!stack.empty()) {
            int node = stack.back();
            stack.pop_back();
            if (node == destination) return true;
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push_back(neighbor);
                }
            }
        }
        return false;
    }
};

两份实现都在压栈时设置 visited，环和重复边不会令顶点二次入栈。行为测试覆盖连通图、不连通图、单顶点和含环图。

复杂度分析​

建表和遍历各访问每条边至多常数次，时间复杂度为 O(V + E)；邻接表、visited 和栈的额外空间为 O(V + E)。

边界与易错点​

  • 无向边必须同时加入 graph[u] 与 graph[v]。
  • source 入栈时就要标记，不能等到弹栈才标记。
  • source 等于 destination 时不需要任何边即可返回真。
  • 顶点总数来自 n，不要只从边集中推断，孤立顶点也存在。

模式迁移​

若输出不再是“能否到达”而是“最少经过多少条边”，把栈换成队列并记录层数；若图的邻居由字符串变换或网格规则生成，则保留相同的 visited 不变量，把邻接表改为按需生成邻居。