Solution: Depth First Search

Grokking the Art of Recursion for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Depth First Search

Table of Contents

Contents are not accessible

Problem Statement

Write Recursive Approach for Depth First Search (DFS).

Given a graph, perform Depth First Search (DFS) traversal on the graph using a recursive approach.

Example 1:

Graph:

    1 -- 2
   / \    \
  3   4 -- 5

Output: 1 2 5 4 3
Explanation: Starting from node 1, we visit its adjacent nodes in order: 2, 5, and 4. From node 4, we visit node 3.

Example 2:

Graph:

   0 -- 1 -- 3
    \  |
      2

Output: 0 1 3 2
Explanation: Starting from node 0, we visit its adjacent nodes in order: 1 and 2. From node 1, we visit node 3.

Example 3:

Graph:

   0 -- 1
   |    |
   3 -- 2

Output: 0 1 2 3
Explanation: Starting from node 0, we visit its adjacent nodes in order: 1 and 3. From node 1, we visit node 2.

Solution

The recursive DFS approach involves visiting each node of the graph and recursively visiting its adjacent nodes. The algorithm can be implemented as follows:

Create a recursive function, dfs, that takes a node and a visited set as parameters.
If the current node is not in the visited set, add it to the visited set and print its value.
Recursively call dfs on each unvisited adjacent node of the current node.

The base case for the recursive function is when the current node is already visited.

Codes

Here is the code for this algorithm:

Python3

. . . .

Time and Space Complexity

The time complexity of the DFS algorithm using recursion is $O(V + E)$ , where V is the number of vertices and E is the number of edges in the graph. This is because, in the worst case, we visit all the vertices and edges of the graph. The space complexity is $O(V)$ , where V is the number of vertices, due to the space used for the visited set.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible