BFS for Graphs

The same assumptions made for the DFS approach apply here too. Here is a summary:

1. Identify the type of the Graph.
2. Build the Adjacency List.
3. For Directed Graphs, keep a visited set to avoid to revisit Nodes.

As for Trees, let's use a Queue to implement the BFS algorithm.

from collections import defaultdict, deque
from typing import DefaultDict, List


class Solution:
    def validPath(
        self, n: int, edges: List[List[int]], source: int, destination: int
    ) -> bool:
        graph = self.buildAdjacencyList(edges)

        return self.bfs(graph, source, destination)

    def bfs(self, graph: DefaultDict[int, List], source: int, destination: int) -> bool:
        visited = {source}
        nodes = deque([source])

        while nodes:
            node = nodes.popleft()
            if node == destination:
                return True

            for neighbor in graph[node]:
                if neighbor not in visited:
                    nodes.append(neighbor)
                    visited.add(neighbor)

        return False

    def buildAdjacencyList(self, edges: List[List[int]]) -> DefaultDict[int, List]:
        graph = defaultdict(list)

        for a, b in edges:
            graph[a].append(b)
            graph[b].append(a)

        return graph