面试题 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。
• 图中可能存在自环和平行边。

Python 解答：
1.BFS

class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        adic = {}
        bdic = [False for i in range(n)]
        for item in graph:
            if item[0] not in adic.keys():
                adic[item[0]] = [item[1]]
            else:
                adic[item[0]].append(item[1])

        def dfs(start, target):
            if start == target:
                return True
            elif start not in adic.keys():
                return False
            else:
                res = False
                bdic[start] = True
                temp = adic[start]
                unvisited = [it for it in temp if not bdic[it]]
                for item in unvisited:
                    res = res or dfs(item, target)
                return res
        return dfs(start, target)

2.BFS

class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        adic = {}
        for item in graph:
            if item[0] not in adic.keys():
                adic[item[0]] = [item[1]]
            else:
                adic[item[0]].append(item[1])
        flag = [False for i in range(n)]
        queue = [start]
        while queue:
            temp = queue.pop(0)
            if temp == target:
                return True
            else:
                flag[temp] = True
                if temp in adic.keys():
                    queue.extend(it for it in adic[temp] if not flag[it])
        return False