图的遍历

面试题 04.01. 节点间通路

BFS

from typing import List
from collections import defaultdict, deque


class Solution:
    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:

        dd = defaultdict(set)
        for a, b in graph:
            dd[a].add(b)

        dq = deque()
        dq.append(start)
        mark = set()
        while dq:
            node = dq.popleft()
            if node == target:
                return True

            if node in mark:
                continue

            dq.extend(dd[node])
            mark.add(node)

        return False

DFS

from typing import List
from collections import defaultdict


class Solution:

    def __init__(self):
        self.dd = defaultdict(int)
        self.start = 0
        self.target = 0
        self.mark = set()
        self.ans = False

    def findWhetherExistsPath(self, n: int, graph: List[List[int]], start: int, target: int) -> bool:
        self.dd = defaultdict(set)
        for a, b in graph:
            self.dd[a].add(b)
        self.start = start
        self.target = target

        return self.dfs(start)

    def dfs(self, node):

        if node == self.target:
            return True
        if node in self.mark:
            return False
        self.mark.add(node)
        for x in self.dd[node]:
            self.ans = self.ans or self.dfs(x)
        return self.ans