DFS for Graphs

Let's apply a DFS algorithm to an actual problem, like Find if Path Exists in Graph.

The first thing to do is to understand which kind of Graph we have to build. The problem clearly specifies that we have a bi-directional graph, which means that the Graph is Undirected.

Now, we can build the actual Graph. In fact, only a list of Edges was provided, which is not a good data structure to use for representing it. So, let's apply the same approach explained before to build the Adjacency List.

We can either use a Recursive or Iterative approach to perform a DFS traversal to the Graph. You can notice that the code is very similar to the DFS Tree Traversal one. The only difference is in the way you get the adjacent nodes.

For a Binary Tree you have the left and right children (or a list of children for a n-ary Tree), whereas for a Graph you have a sequence of Neighbors.

Moreover, especially for the Directed Graphs, we need to keep a set of visited Nodes to avoid to revisit a Node. For a Tree we do not have such problem, since we cannot go back to the parent node from its children.

This is the Recursive approach:

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


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

        return self.dfs(graph, source, destination, set())

    def dfs(
        self, graph: DefaultDict[int, List], source: int, destination: int, visited: Set
    ) -> bool:
        if source in visited:
            return False

        if source == destination:
            return True

        visited.add(source)
        for neighbor in graph[source]:
            if self.dfs(graph, neighbor, destination, visited):
                return True

        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

And this is the Iterative one. As usual, we can use a Stack to emulate the recursive calls.

from collections import defaultdict
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.dfs(graph, source, destination)

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

        while nodes:
            node = nodes.pop()
            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