DFS Traversal in Graph | Explained using Code

Learn how to perform a DFS Traversal in Graph represented by an adjacency list using simple Python recursion. Step by step code, dry run, and complexity analysis included, no prior experience needed!

What the Problem Asks

DFS Traversal of Graph
Given a graph as an adjacency list, start at node 0 and perform a DFS. Return the list of nodes in the order they’re first visited.

Input:

• adj: A list of length N, where adj[u] is a list of neighbors of node u.

Output:

• A list of node indices in the exact order DFS visits them, starting from 0.

Intuition & Approach

DFS Basics:

• You start at a node, mark it visited, then recursively explore each unvisited neighbor as deeply as possible before backtracking.

Why Recursion?

• The call stack naturally remembers the path you’ve taken. When you finish one branch, it “pops back” and continues with siblings.

Key Steps:

• Maintain a visited array to avoid revisiting nodes (and infinite loops).
• Maintain a result list to record the visit order.
• Write a helper dfs_algo(node) that:
  1. Marks node visited and appends it to result.
  2. Loops through each neighbor; if it’s unvisited, recurses into that neighbor.

Code Implementation

class Solution:
    def dfs_algo(self, node, adj, visited, result):
        # 1. Visit this node
        result.append(node)
        visited[node] = 1

        # 2. Recurse on each unvisited neighbor
        for neighbor in adj[node]:
            if not visited[neighbor]:
                self.dfs_algo(neighbor, adj, visited, result)

    def dfs(self, adj):
        total_nodes = len(adj)
        visited = [0] * total_nodes  # 0 = unvisited, 1 = visited
        result = []

        # Start DFS from node 0
        self.dfs_algo(0, adj, visited, result)
        return result

Code Explanation

visited list:

• Tracks whether each node has already been explored.

result list:

• Records the order in which nodes are visited.

dfs_algo(node, adj, visited, result):

• Visit: Append node to result and mark visited[node] = 1.
• Explore neighbors: For every neighbor in adj[node], if it’s unvisited, call dfs_algo(neighbor, …) recursively.

dfs(adj):

• Initializes visited and result.
• Kicks off recursion at node 0.
• Returns the filled result list.

Dry Run Example

Graph:

0: [1, 2]
1: [0, 3]
2: [0, 4]
3: [1]
4: [2]

• Start at 0:
  • Visit 0 → result = [0].
  • Neighbors: 1, 2.
• Go to 1:
  • Visit 1 → result = [0,1].
  • Neighbors: 0 (already visited), 3.
• Go to 3:
  • Visit 3 → result = [0,1,3].
  • Neighbor: 1 (visited) → backtrack to 1, then back to 0.
• Back at 0, next neighbor 2:
  • Visit 2 → result = [0,1,3,2].
  • Neighbors: 0 (visited), 4.
• Go to 4:
  • Visit 4 → result = [0,1,3,2,4].
  • Neighbor: 2 (visited), done.

Final DFS order: [0, 1, 3, 2, 4]

Time & Space Complexity

• Time Complexity:
  • We visit each node exactly once and examine each edge once → O(N + 2E), where N = nodes, E = edges.
• Space Complexity:
  • O(N) for the visited and result lists, plus O(N) recursion stack in the worst case (e.g., a long chain).

Conclusion

Depth-First Search via recursion is straightforward and intuitive. By marking nodes as visited before recursing, you avoid cycles and capture a clear visit order. Mastering this pattern equips you to tackle many graph problems—from connectivity checks to path finding—both on GeeksforGeeks and in coding interviews. Happy exploring!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.