程序员面试金典 - 面试题 04.01. 节点间通路

题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。

示例 1:

• 输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
• 输出：true

示例 2:

• 输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
• 输出 true

提示：

• 节点数量 n 在[0, 1e5]范围内。
• 节点编号大于等于 0 小于 n。
• 图中可能存在自环和平行边。

题目思考

1. 需要预处理哪些信息?
2. 可以使用哪些算法来判断连通?

解决方案

思路

• 根据题目给定信息, 我们可以得到对应的邻接表, 即{u:[v1,v2,...,vn]}字典, 其中 v1,v2,...,vn 是 u 指向的所有节点
• 有了这个邻接表, 我们就可以利用经典的 DFS 或者 BFS 算法来判断是否连通了
• 两个算法思路类似, 都是传入起点, 然后利用邻接表依次遍历相邻的节点, 直到遍历到终点或者遍历完当前的连通分量
• 注意还需要额外的 visit 集合来避免节点重复被遍历
• 下面代码分别提供了 BFS 和 DFS 的方案, 并添加了必要的注释方便大家理解

复杂度

• 时间复杂度 O(N): 每个节点只需要遍历一遍
• 空间复杂度 O(N): 使用了额外 visit 集合

代码

方法 1 - DFS 判断连通

import collections


class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int,
                              target: int) -> bool:
        # 方法1: 转成邻接表然后DFS判断
        if start == target:
            # 起点和终点相同, 直接连通
            return True
        # 先建立邻接表
        maps = collections.defaultdict(list)
        for x, y in graph:
            maps[x].append(y)
        # 然后DFS
        # 注意使用v集合来避免重复遍历
        v = {start}

        def dfs(x):
            if x == target:
                # 当前就是终点, 直接返回true
                return True
            for nex in maps[x]:
                if nex not in v:
                    v.add(nex)
                    if dfs(nex):
                        # 找到终点了
                        return True
            # 没找到终点
            return False

        return dfs(start)

方法 2 - BFS 判断连通

import collections


class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int,
                              target: int) -> bool:
        # 方法2: 转成邻接表然后BFS判断
        if start == target:
            # 起点和终点相同, 直接连通
            return True
        # 先建立邻接表
        maps = collections.defaultdict(list)
        for x, y in graph:
            maps[x].append(y)
        # 然后BFS
        q = [start]
        v = set(q)
        for x in q:
            for nex in maps[x]:
                if nex == target:
                    # 这里直接判断nex是否为target, 而不是等遍历到x再判断, 提前加速找终点
                    return True
                if nex not in v:
                    v.add(nex)
                    q.append(nex)
        return False

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊