DFS Depth First Search on Graph in DSA Python

Mental Model

DFS explores as far as possible along each branch before backtracking. It dives deep into one path before trying others.

Analogy: Imagine exploring a maze by always taking the first unexplored path you find, going deep until you hit a dead end, then backtracking to try other paths.

Graph adjacency list:
0 -> [1, 2]
1 -> [2]
2 -> [0, 3]
3 -> [3]
Start at node 2 ↑

Dry Run Walkthrough

Input: Graph edges: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; start DFS at node 2

Goal: Visit all nodes reachable from node 2 using DFS order

Step 1: Start DFS at node 2, mark 2 visited

Visited: {2}
Stack: [2]

Why: We begin exploring from node 2

Step 2: Explore neighbor 0 of node 2, mark 0 visited

Visited: {2, 0}
Stack: [2, 0]

Why: Go deep to first neighbor 0

Step 3: Explore neighbor 1 of node 0, mark 1 visited

Visited: {2, 0, 1}
Stack: [2, 0, 1]

Why: Continue deep exploration to neighbor 1

Step 4: Neighbor 1 has neighbor 2 already visited, backtrack from 1

Visited: {2, 0, 1}
Stack: [2, 0]

Why: No new nodes from 1, backtrack

Step 5: Back at node 0, neighbor 2 already visited, backtrack from 0

Visited: {2, 0, 1}
Stack: [2]

Why: No new nodes from 0, backtrack

Step 6: At node 2, explore neighbor 3, mark 3 visited

Visited: {2, 0, 1, 3}
Stack: [2, 3]

Why: Explore next neighbor 3

Step 7: Node 3 has neighbor 3 already visited, backtrack from 3

Visited: {2, 0, 1, 3}
Stack: [2]

Why: No new nodes from 3, backtrack

Step 8: Back at node 2, all neighbors visited, DFS complete

Visited: {2, 0, 1, 3}
Stack: []

Why: All reachable nodes visited

Result:

Visited nodes in DFS order: 2 -> 0 -> 1 -> 3

Annotated Code

DSA Python

class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.adj = [[] for _ in range(vertices)]

    def add_edge(self, u, v):
        self.adj[u].append(v)

    def dfs_util(self, v, visited, result):
        visited[v] = True  # mark current node visited
        result.append(v)   # add to result path
        for neighbor in self.adj[v]:  # explore neighbors
            if not visited[neighbor]:
                self.dfs_util(neighbor, visited, result)  # recursive deep dive

    def dfs(self, start):
        visited = [False] * self.V
        result = []
        self.dfs_util(start, visited, result)
        return result

# Driver code
if __name__ == '__main__':
    g = Graph(4)
    g.add_edge(0, 1)
    g.add_edge(0, 2)
    g.add_edge(1, 2)
    g.add_edge(2, 0)
    g.add_edge(2, 3)
    g.add_edge(3, 3)

    dfs_result = g.dfs(2)
    print(' -> '.join(map(str, dfs_result)))

visited[v] = True # mark current node visited

Mark current node as visited to avoid revisiting

result.append(v) # add to result path

Record the node in DFS traversal order

for neighbor in self.adj[v]: # explore neighbors

Check each neighbor to continue DFS

if not visited[neighbor]:

Only visit neighbors not visited yet

self.dfs_util(neighbor, visited, result) # recursive deep dive

Recursively explore neighbor deeply before backtracking

Output

2 -> 0 -> 1 -> 3

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for the visited list and recursion stack in worst case

vs Alternative: Compared to BFS which uses a queue and explores neighbors level by level, DFS uses recursion or stack and explores deep paths first; both have similar time but different traversal order

Edge Cases

Graph with no edges

DFS visits only the start node

DSA Python

visited[v] = True  # mark current node visited

Graph with single node

DFS visits that single node and stops

DSA Python

visited[v] = True  # mark current node visited

Graph with cycles

Visited list prevents infinite loops by skipping visited nodes

DSA Python

if not visited[neighbor]:

When to Use This Pattern

When you need to explore all possible paths deeply or check connectivity in a graph, reach for DFS because it dives deep before backtracking, useful for pathfinding and cycle detection.

Common Mistakes

Mistake: Not marking nodes as visited before recursive calls
Fix: Mark the node visited immediately when processing it to avoid infinite recursion

Mistake: Visiting neighbors without checking if already visited
Fix: Always check visited status before recursive DFS call

Summary

DFS visits nodes by going deep along each path before backtracking.

Use DFS when you want to explore all paths or check connectivity in graphs.

The key insight is to mark nodes visited and explore neighbors recursively to avoid loops.

Practice

1. What does DFS (Depth First Search) do when exploring a graph?

easy

A. It explores as far as possible along each branch before backtracking.

B. It explores all neighbors at the current depth before going deeper.

C. It visits nodes randomly without any order.

D. It only visits nodes with the highest value first.

Solution

1. Step 1: Understand DFS traversal

   DFS explores a graph by going deep into one branch before backtracking to explore others.

2. Step 2: Compare with other traversal methods

   BFS explores neighbors level by level, but DFS goes deep first.

3. Final Answer:

   It explores as far as possible along each branch before backtracking. -> Option A

4. Quick Check:

   DFS = deep exploration first [OK]

Hint: DFS means go deep first, then backtrack [OK]

Common Mistakes:

• Confusing DFS with BFS
• Thinking DFS visits nodes randomly
• Assuming DFS visits nodes by value

2. Which of the following is the correct Python syntax to start a DFS function on a graph represented as adjacency list graph from node start?

easy

A. def dfs(start, graph):

B. def dfs(graph, start):

C. def dfs(graph):

D. def dfs(start):

Solution

1. Step 1: Identify required parameters for DFS

   DFS needs the graph and the starting node to begin traversal.

2. Step 2: Check function signature correctness

   def dfs(graph, start): correctly defines a function with parameters (graph, start).

3. Final Answer:

   def dfs(graph, start): -> Option B

4. Quick Check:

   DFS needs graph and start node [OK]

Hint: DFS function needs graph and start node parameters [OK]

Common Mistakes:

• Swapping parameter order incorrectly
• Missing one of the parameters
• Using only one parameter when two are needed

3. What is the output of the following DFS traversal starting from node 0?

graph = {0: [1, 2], 1: [2], 2: [0, 3], 3: [3]}
visited = set()
def dfs(node):
    if node not in visited:
        print(node, end=' ')
        visited.add(node)
        for neighbor in graph[node]:
            dfs(neighbor)
dfs(0)

medium

A. 0 3 2 1

B. 0 2 3 1

C. 0 1 3 2

D. 0 1 2 3

Solution

1. Step 1: Start DFS from node 0

   Visit 0, mark visited. Neighbors: 1, 2.

2. Step 2: Visit neighbor 1

   Visit 1, mark visited. Neighbor: 2.

3. Step 3: Visit neighbor 2

   Visit 2, mark visited. Neighbors: 0 (visited), 3.

4. Step 4: Visit neighbor 3

   Visit 3, mark visited. Neighbor: 3 (already visited).

5. Final Answer:

   0 1 2 3 -> Option D

6. Quick Check:

   DFS order = 0 1 2 3 [OK]

Hint: Follow neighbors depth-first, avoid revisiting nodes [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Revisiting already visited nodes
• Confusing BFS order with DFS

4. Find the error in this DFS code snippet and select the fix:

graph = {0: [1], 1: [2], 2: []}
visited = set()
def dfs(node):
    if node in visited:
        return
    print(node)
    for neighbor in graph[node]:
        dfs(neighbor)
dfs(0)

medium

A. Add 'visited.add(node)' after printing node to mark it visited.

B. Change 'if node in visited' to 'if node not in visited'.

C. Remove the 'return' statement inside the if condition.

D. Add 'visited.remove(node)' after recursive calls.

Solution

1. Step 1: Identify missing visited marking

   The code never adds nodes to visited, so it revisits nodes infinitely.

2. Step 2: Fix by adding visited marking

   Adding 'visited.add(node)' after printing marks node as visited to avoid revisits.

3. Final Answer:

   Add 'visited.add(node)' after printing node to mark it visited. -> Option A

4. Quick Check:

   Mark visited after visiting node [OK]

Hint: Always add node to visited set after visiting [OK]

Common Mistakes:

• Forgetting to mark nodes visited
• Incorrect if condition logic
• Removing nodes from visited incorrectly

5. Given a directed graph represented as adjacency list:

graph = {0: [1, 2], 1: [2], 2: [3], 3: [1]}

Write the DFS traversal order starting from node 0 that detects cycles by tracking recursion stack. What is the order of nodes visited before detecting a cycle?

hard

A. 0 1 2

B. 0 2 3 1

C. 0 1 2 3

D. 0 2 1 3

Solution

1. Step 1: Start DFS from node 0 and track recursion stack

   Visit 0, then 1, then 2, then 3. At 3, neighbor 1 is in recursion stack, cycle detected.

2. Step 2: List nodes visited before cycle detection

   Nodes visited in order: 0, 1, 2, 3 before cycle found.

3. Final Answer:

   0 1 2 3 -> Option C

4. Quick Check:

   DFS with cycle detection visits 0 1 2 3 [OK]

Hint: Track recursion stack to detect cycles during DFS [OK]

Common Mistakes:

• Ignoring recursion stack for cycle detection
• Stopping traversal too early
• Visiting nodes in wrong order