寻找图中是否存在路径

难度: Easy

有一个具有 n 个顶点的双向图，其中每个顶点标记从 0 到 n - 1（包含 0 和 n - 1）。图中的边用一个二维整数数组 edges 表示，其中 edges[i] = [u_i, v_i] 表示顶点 ui 和顶点 vi 之间的双向边。每个顶点对由 最多一条 边连接，并且没有顶点存在与自身相连的边。

请你确定是否存在从顶点 source 开始，到顶点 destination 结束的 有效路径 。

给你数组 edges 和整数 n、source 和 destination，如果从 source 到 destination 存在 有效路径 ，则返回 true，否则返回 false 。

示例 1：

输入：n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2
输出：true
解释：存在由顶点 0 到顶点 2 的路径:
- 0 → 1 → 2 
- 0 → 2

示例 2：

输入：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5
输出：false
解释：不存在由顶点 0 到顶点 5 的路径.

提示：

1 <= n <= 2 * 10⁵
0 <= edges.length <= 2 * 10⁵
edges[i].length == 2
0 <= u_i, v_i <= n - 1
u_i != v_i
0 <= source, destination <= n - 1
不存在重复边
不存在指向顶点自身的边

Submission

运行时间: 111 ms

内存: 78.5 MB

# class Solution:
#     def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
#         if [source,destination] in edges or [destination,source] in edges: return True 
#         if source==destination: return True
#         s0=[]
#         hasnew={}
#         visit=set()
#         for x,y in edges:
#             hasnew={x,y}-visit
            
#             if len(hasnew)==2:
#                 s0.append(hasnew)
#                 visit|={x,y}
#             elif len(hasnew)==0:
#                 a,b=-1,-1
#                 for i,s in enumerate(s0):
#                     if x in s:
#                         a=i
#                         if b!=-1:
#                             if a!=b:
#                                 s0[b]|=s
#                                 if source in s0[b]  and destination in s0[b]:
#                                     return True
#                                 s0.pop(a)
#                             break

#                     if y in s:
#                         b=i
#                         if a!=-1:
#                             if a!=b:
#                                 s0[a]|=s
#                                 if source in s0[a]  and destination in s0[a]:
#                                     return True
#                                 s0.pop(b)
#                             break    
#             else:
#                 visit|=hasnew
#                 tx=list({x,y}-hasnew)[0]
#                 for i,s in enumerate(s0):
#                     if tx in s:
#                         s0[i]|=hasnew
#                         if source in s0[i]  and destination in s0[i]:
#                             return True
#                         break
            

#         return False                

class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        reachable =set([source])
        nE = len(edges)
        while 1:
            n = len(reachable)
            for ii in range(nE):
                if edges[ii][0] in reachable:
                    reachable.add(edges[ii][1])
                elif edges[ii][1] in reachable:
                    reachable.add(edges[ii][0])
            if destination in reachable:
                return True
            if len(reachable) == n:
                return False

Explain

该题解采用了一种迭代的方法来判断从给定的源点source是否可以到达目标点destination。首先定义一个集合reachable，初始时只包括源点source。然后不断迭代，尝试通过边集edges中的边来扩展reachable集合。在每次迭代中，遍历所有的边，若边的任一顶点已在reachable中，则将另一顶点加入reachable。如果在任意迭代后destination出现在reachable中，则返回true。如果在某次迭代后reachable的大小不再增加，说明所有可达的顶点都已被找到，若此时destination仍未被包含在内，则返回false。

时间复杂度: O(E * V)

空间复杂度: O(V)

# class Solution:
#     def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
#         reachable =set([source])  # 初始化包含源点的可达集合
#         nE = len(edges)  # 边的数量
#         while 1:  # 不断尝试扩展reachable集合
#             n = len(reachable)  # 记录当前可达集合的大小
#             for ii in range(nE):  # 遍历所有边
#                 if edges[ii][0] in reachable:  # 如果边的一个顶点已在reachable中
#                     reachable.add(edges[ii][1])  # 添加另一个顶点
#                 elif edges[ii][1] in reachable:  # 同上，反向检查
#                     reachable.add(edges[ii][0])
#             if destination in reachable:  # 如果目标点已在可达集合中
#                 return True  # 返回true
#             if len(reachable) == n:  # 如果可达集合的大小未增加
#                 return False  # 返回false

Explore

我的算法没有专门处理图中环的特殊逻辑，但由于使用了集合（set）来存储已经到达的顶点，该算法自然可以处理环的存在。当一个顶点通过环路再次到达时，由于它已经存在于集合中，不会被重复添加，因此算法不会因环的存在而陷入无限循环。

在顶点非常多但边较少的情况下，我的算法可能不是最优的，因为它每次迭代都会检查所有边，即使大多数顶点未与边直接相连。对于这种稀疏图，使用邻接表而不是边列表可以更高效地进行图遍历，例如通过深度优先搜索（DFS）或广度优先搜索（BFS）。这样可以只检查与已访问顶点直接相连的顶点，从而减少不必要的检查和存储。

该算法可以处理边中存在的重复元素。由于使用了集合来存储已达到的顶点，即使边[1, 2]重复多次出现，顶点2只会在第一次被发现时加入到集合中。因此，重复的边不会影响最终的结果，但会造成算法在处理这些重复边时的性能浪费，因为它需要多次检查这些边。

是的，如果source和destination是同一个顶点，算法可以立即返回结果。在算法的初始设定中，源点source已经被添加到可达集合中，因此如果源点和目标点相同，那么目标点已在可达集合中，算法将立即检测到这一点并返回True。