Find if Path Exists in Graph

Q: 在图中查找是否存在路径的时间复杂度是多少？

对于 n 个节点和 m 条边，BFS 或 DFS 的时间和空间复杂度为 O(n + m) 。按大小合并并采用路径减半的并查集，时间复杂度为 O(n + m·α(n)) ，空间复杂度为 O(n) ，而 α(n) 在实际应用中是一个很小的常数。

Q: 在并查集中，路径压缩和按大小合并有什么作用？

它们会让树保持较浅，这样 find 就能保持快速。按大小合并会把较小的树挂到较大的树下面，因此只有当一个节点所属的组至少翻倍时，它的深度才会增加，这样深度就不会超过 log n 。每次运行 find 时，路径压缩或路径折半都会缩短到根节点的路径。

简单图并查集

+10

一个无向图有 n 个节点，编号从 0 到 n-1。edges 中的每个条目 [u, v] 都连接节点 u 和 v，你可以沿任一方向经过这条边。如果你可以沿着边从 source 到达 destination，则返回 true，否则返回 false。节点始终可以到达自身。

函数

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: 节点数量
edgesinteger-2d-array: 边，每条边都是一对相连的节点 [u, v]
sourceinteger: 起始节点
destinationinteger: 你想要到达的节点
返回值boolean: 某条路径是否连接源点和目标点

约束条件

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v]，其中 0 ≤ u, v ≤ n-1 且 u ≠ v
没有边会重复出现，无论方向如何。
0 ≤ source, destination ≤ n-1

示例

输入: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
输出: true
解释: 路径 0 → 1 → 2 → 3 使用了三条边，因此节点 3 是可达的。节点 4 和 5 构成了一个独立部分，路径不需要经过那里。

输入: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
输出: false
解释: 从节点 2 出发，你可以到达 0，然后到达 1，除此之外什么也到达不了。节点 4 只与节点 3 相连，并且没有边连接 {0, 1, 2} 和 {3, 4}，所以答案是 false。

进阶

假设边是单向的：[u, v] 只允许你从 u 走到 v。三种方法中，哪些仍然可行？你需要对它们做哪些修改？

提示

逐个打开提示，每个都会多透露一点。

已打开 0/3

题解

问题是，source 和 destination 是否位于图中同一个连通部分。通过邻接表进行广度优先搜索，可以在每个节点和边上各探索一次，从而得出答案。并查集则通过读取边来合并集合，完全不需要邻居列表。

持续扫描边缘，直到没有任何变化

结果正确，但无法在最大的测试中运行完毕

思路

将 source 标记为已到达，然后遍历边列表。若一条边的一端已标记，你就能到达另一端，因此将另一端标记。重复此过程，直到某一轮没有标记任何新节点，或 destination 已被标记。

距离 source 为 k 的节点最迟会在第 k 轮被标记；而节点只有通过一条连接到已标记节点的边才会被标记，因此答案是正确的。开销取决于边的顺序。如果路径是从远端开始反向列出的，每轮只会标记一个节点：一条有 5000 条边的路径需要 5000 轮，也就是检查 2.5 × 10^7 条边。

算法

创建 reached，并且只标记 source。
遍历每条边 [u, v]。如果恰好有一个端点已标记，就标记另一个端点，并记录发生了变化。
只要发生了变化且 destination 仍未标记，就重复遍历。
返回 destination 是否已标记。

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

广度优先搜索

思路

扫描过程会重新读取很久以前就已确定端点的边。你可以改为为每个节点列出与它相连的节点，因为每条边都可以双向遍历，所以要把它加入两边的列表。然后用队列从 source 开始向外探索，将所有尚未访问过的邻居入队。

将节点入队时就标记为已访问。这样每个节点都不会重复入队，即使遇到 0 → 1 → 2 → 0 这样的环，搜索也会结束。如果队列在 destination 出队前就已清空，说明你已经访问了 source 能到达的所有节点。每个节点只入队一次，每条边都会从两端检查：对于 m 条边，时间和空间复杂度都是 O(n + m)。

算法

构建邻接表：对于每条边 [u, v]，将 v 添加到 u 的列表中，并将 u 添加到 v 的列表中。
将 source 标记为已访问，并将它放入队列。
从队首取出一个节点。如果它是 destination，则返回 true。
将每个尚未访问的邻居标记为已访问，并加入队列。
队列为空时，返回 false。

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

并查集

思路

你需要知道一条路径是否存在，而不是它是什么。先让每个节点各自属于一个组。一条边 [u, v] 表示 u 和 v 属于同一组，因此要合并它们所在的组。处理完所有边后，当且仅当 source 和 destination 属于同一组时，它们才连通。

把每个组存成一棵由 parent 链接构成的树；根节点代表这个组，find(x) 会沿着链接向上找到它。在第二个示例中，[0, 1] 和 [0, 2] 构成 {0, 1, 2}，而 [3, 4] 构成 {3, 4}，因此 find(2) 和 find(4) 会返回不同的根节点。

把较小的树挂在较大的树下面，并在 find 期间让每个节点指向它的祖父节点，可以保持树的扁平。这样，每次操作的开销都是 α(n)，即反阿克曼函数；对于任何实际输入，它都小于 5。只存储 parent 和 size：空间复杂度为 O(n)。

算法

为每个节点设置 parent[x] = x 和 size[x] = 1。
对于每条边 [u, v]，找到两端的根节点 a 和 b。
如果它们不同，就把较小集合的根挂到另一个根下面，并将两者的大小相加。
返回 find(source) 是否等于 find(destination)。

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

易错点和边界情况

每条边只按一个方向添加。对于 edges = [[1, 0]]，单向列表无法找到从 0 到 1 的路径。
取出节点时才将其标记为已访问。这样，在它之前处理的每个邻居都会让它进入队列一次，最多会有 2m 个条目，而不是 n 个。
忽略了 source 可能等于 destination。即使该节点没有边，答案也是 true。
在较长的路径上使用递归 DFS。经过 5000 个节点的路径会产生 5000 层嵌套调用，超过了 Python 默认的 1000 层限制。请使用队列或显式栈。
在并查集中比较 parent[source] 和 parent[destination]。只有根节点能表示一个分组，因此要比较 find(source) 和 find(destination)。

常见问题3

我应该使用 BFS、DFS 还是并查集来检查路径是否存在？

这三种算法的时间复杂度都是线性的或接近线性的。BFS 和 DFS 一旦到达目标节点就可以停止，并且可以返回路径本身。并查集不需要邻接表，适合处理同一张图上的许多连通性问题：合并完成后，每个问题只需调用两次 find。

在图中查找是否存在路径的时间复杂度是多少？

对于 n 个节点和 m 条边，BFS 或 DFS 的时间和空间复杂度为 O(n + m)。按大小合并并采用路径减半的并查集，时间复杂度为 O(n + m·α(n))，空间复杂度为 O(n)，而 α(n) 在实际应用中是一个很小的常数。

在并查集中，路径压缩和按大小合并有什么作用？

它们会让树保持较浅，这样 find 就能保持快速。按大小合并会把较小的树挂到较大的树下面，因此只有当一个节点所属的组至少翻倍时，它的深度才会增加，这样深度就不会超过 log n。每次运行 find 时，路径压缩或路径折半都会缩短到根节点的路径。

def validPath(n, edges, source, destination):
    # 在这里编写代码

测试 #1

测试 #2

参数

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

预期输出

true