Depth First Search

Python C++

  • Input:
    • directed or undirected graph with N nodes and M edges
    • source node
  • Output:
    • array reachable of length N, where:
      • reachable[i] = 1 if node i is reachable from source node
      • reachable[i] = 0 otherwise
  • Time complexity: $O(N + M)$

Description

The idea behind DFS is to go as deep into the graph as possible, and backtrack once you are at a node without any unvisited adjacent node.

We start the search at one node. After visiting a node, we further perform a DFS for each adjacent node that we haven't visited before. This way we visit all node that are reachable from the starting node.

Example

Let's see how the Depth First Search algorithm works with an example. We use an undirected graph with 5 nodes.

We start from node 1, the DFS algorithm starts by setting reachable[1] = 1 and going to node 2 - first unvisited neighbour of node 1.

DFS visit node 2, set reachable[2] = 1 and go to node 3 - first unvisited neighbour of node 2.

DFS visit node 3, set reachable[3] = 1 and go to node 5 - first unvisited neighbour of node 3.

DFS visit node 5, set reachable[5] = 1 and backtrack to node 3 because node 5 has not any unvisited neighbour.

DFS backtrack from node 3 to node 2 because node 3 has not any unvisited neighbour.

DFS backtrack from node 2 to node 1 because node 2 has not any unvisited neighbour.

DFS backtrack to node 1 and go to node 4 - next unvisited neighbour of node 1.

DFS visit node 4, set reachable[4] = 1 and backtrack to node 1 because node 5 has not any unvisited neighbour. The Depth First Search has completed.

Code

Python 

                        def dfs(
                            graph: Dict[int, List[int]],
                            reachable: Dict[int, bool],
                            node: int,
                        ) -> Dict[int, bool]:
                            reachable[node] = True
                            for neighbour in graph[node]:
                                if False == reachable[neighbour]:
                                    dfs(graph, reachable, neighbour)
                            return reachable
C++