DFS Depth First Search on Graph in DSA Python - Deep Dive

Overview - DFS Depth First Search on Graph

What is it?

Depth First Search (DFS) is a way to explore all the points (called nodes) in a graph by going as deep as possible before backtracking. Imagine starting at one node and moving to a connected node, then to another connected node, and so on, until you cannot go further. Then you step back and explore other paths. This method helps find paths, check connections, and understand the structure of the graph.

Why it matters

Without DFS, exploring complex networks like social connections, maps, or computer networks would be slow and confusing. DFS helps quickly find if two points are connected, discover all reachable points, or detect loops. It is a foundation for many algorithms that power search engines, route planning, and even puzzle solving.

Where it fits

Before learning DFS, you should understand what graphs are and how they represent connections. After DFS, you can learn Breadth First Search (BFS), shortest path algorithms, and graph traversal optimizations.

Mental Model

Core Idea

DFS explores a graph by going deep along one path until it can't go further, then backtracks to explore other paths.

Think of it like...

Imagine exploring a maze by always taking the first unexplored path you find, going as far as you can, then turning back when you hit a dead end to try other routes.

Start
  │
  ▼
Node A
  │
  ▼
Node B
  │
  ▼
Node C (dead end)
  ▲
  │
Backtrack to B
  │
  ▼
Node D
  ...

This shows DFS going deep from A to C, then backtracking to B to explore D.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes (points) connected by edges (lines).

A graph is like a map of cities (nodes) connected by roads (edges). Each city can connect to one or many others. Graphs can be directed (one-way roads) or undirected (two-way roads). Understanding this helps us know what DFS will explore.

Result

You can picture a graph as a network of connected points.

Knowing what a graph is and how nodes connect is essential before exploring how to traverse it.

2

Foundation

What is Depth First Search (DFS)?

Concept: DFS is a method to visit all nodes by going deep before wide.

Starting from one node, DFS visits a connected node, then another connected node from there, continuing until no new nodes are found. Then it backtracks to explore other paths. This ensures every reachable node is visited.

Result

You understand DFS as a deep exploration method.

Grasping the deep-then-backtrack pattern is key to understanding DFS.

3

Intermediate

Implementing DFS with Recursion

🤔Before reading on: Do you think recursion means repeating the same function inside itself or something else? Commit to your answer.

Concept: DFS can be implemented by a function calling itself to explore nodes deeply.

In Python, DFS uses a function that visits a node, marks it visited, then calls itself on each unvisited neighbor. This repeats until all connected nodes are visited. Example: visited = set() def dfs(node, graph): if node in visited: return visited.add(node) for neighbor in graph[node]: dfs(neighbor, graph)

Result

The function visits all nodes reachable from the start node.

Understanding recursion helps see how DFS naturally explores deep paths without extra data structures.

4

Intermediate

Using Stack for DFS Instead of Recursion

🤔Before reading on: Do you think DFS can work without recursion? Commit to yes or no.

Concept: DFS can also use a stack to keep track of nodes to visit, simulating recursion.

Instead of calling itself, DFS can push nodes onto a stack. It pops a node, visits it, then pushes its neighbors. This repeats until the stack is empty. Example: visited = set() stack = [start_node] while stack: node = stack.pop() if node not in visited: visited.add(node) stack.extend(graph[node])

Result

DFS visits all reachable nodes using a stack instead of recursion.

Knowing DFS can be done with a stack reveals its underlying process and helps avoid recursion limits.

5

Intermediate

Handling Cycles and Visited Nodes

🤔Before reading on: Do you think DFS can get stuck in loops if it revisits nodes? Commit yes or no.

Concept: DFS must track visited nodes to avoid infinite loops in graphs with cycles.

Graphs can have cycles where nodes connect back to earlier nodes. Without marking visited nodes, DFS would revisit the same nodes endlessly. Using a visited set prevents this by skipping nodes already explored.

Result

DFS safely explores graphs with cycles without infinite loops.

Recognizing the need to track visited nodes prevents common bugs and infinite loops.

6

Advanced

DFS for Connected Components and Path Finding

🤔Before reading on: Do you think DFS can find all separate groups in a graph or just one? Commit your answer.

Concept: DFS can find all connected groups and paths between nodes by repeated exploration.

By running DFS from unvisited nodes repeatedly, you can find all connected components (groups of nodes connected together). Also, by remembering the path taken, DFS can find a route from one node to another. Example: To find connected components, run DFS on each unvisited node and count how many times you start DFS.

Result

You can identify separate groups and paths in a graph using DFS.

Understanding DFS beyond single runs unlocks its power for graph analysis.

7

Expert

DFS in Practice: Recursive Limits and Iterative Deepening

🤔Before reading on: Do you think deep recursion in DFS can cause problems in real programs? Commit yes or no.

Concept: Deep recursion in DFS can cause stack overflow; iterative deepening DFS combines DFS depth control with BFS completeness.

In very large or deep graphs, recursive DFS can exceed the call stack limit, crashing programs. Iterative Deepening DFS runs DFS with increasing depth limits, combining DFS's space efficiency with BFS's completeness. This approach avoids deep recursion and finds shortest paths in some cases. Example: Run DFS with depth limit 1, then 2, then 3, etc., until target found.

Result

You learn how to handle DFS limits and improve search in large graphs.

Knowing DFS limitations and advanced variants prepares you for real-world graph challenges.

Under the Hood

DFS works by maintaining a stack of nodes to visit, either implicitly via recursion or explicitly via a data structure. Each node is visited once, and its neighbors are added to the stack. The process continues until no nodes remain to explore. The visited set prevents revisiting nodes, avoiding infinite loops in cyclic graphs.

Why designed this way?

DFS was designed to explore graphs deeply because many problems require exploring paths fully before trying alternatives. Using recursion or a stack matches the natural depth-first exploration pattern. Alternatives like BFS explore breadth-wise but need more memory. DFS's design balances simplicity and efficiency for many graph problems.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Visit Node  │
│ Mark Visited│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Add Neighbors│
│ to Stack or  │
│ Recursive Call│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Pop Next    │
│ Node to Visit│
└──────┬──────┘
       │
       ▼
   Repeat until
   stack empty

Myth Busters - 4 Common Misconceptions

Quick: Does DFS always find the shortest path between two nodes? Commit yes or no.

Common Belief: DFS always finds the shortest path between two nodes.

Reality: DFS does not guarantee the shortest path; it explores deeply and may find longer paths first.

Why it matters: Relying on DFS for shortest paths can lead to inefficient or incorrect solutions in routing or navigation.

Quick: Can DFS work without tracking visited nodes in all graphs? Commit yes or no.

Common Belief: DFS can safely run without marking visited nodes.

Reality: Without marking visited nodes, DFS can get stuck in infinite loops in graphs with cycles.

Why it matters: Not tracking visited nodes causes programs to hang or crash due to infinite recursion or loops.

Quick: Is recursion the only way to implement DFS? Commit yes or no.

Common Belief: DFS must be implemented using recursion.

Reality: DFS can be implemented using an explicit stack, avoiding recursion and its limits.

Why it matters: Knowing iterative DFS helps avoid stack overflow and improves control in large graphs.

Quick: Does DFS visit nodes in the order they appear in the graph data structure? Commit yes or no.

Common Belief: DFS visits nodes in the order they are stored in the graph.

Reality: DFS visits nodes based on the order neighbors are explored, which depends on data structure and implementation.

Why it matters: Assuming fixed order can cause confusion when debugging or comparing DFS outputs.

Expert Zone

1

The order of neighbors visited in DFS affects traversal path and can change results in algorithms like topological sort.

2

DFS can be adapted to detect cycles by tracking recursion stack in addition to visited nodes.

3

In directed graphs, DFS helps identify strongly connected components using advanced algorithms like Tarjan's.

When NOT to use

DFS is not ideal when shortest paths are needed; use Breadth First Search (BFS) instead. For weighted graphs, algorithms like Dijkstra's or A* are better. Also, DFS can cause stack overflow in very deep graphs; iterative or limited-depth methods are preferred.

Production Patterns

DFS is used in maze generation, puzzle solving, detecting cycles in dependency graphs, and analyzing social networks. It is also a building block in algorithms like topological sorting, connected components detection, and solving puzzles like Sudoku.

Connections

Breadth First Search (BFS)

BFS explores graphs level by level, opposite to DFS's deep exploration.

Understanding DFS helps grasp BFS as its complementary approach, useful for shortest paths and level order traversal.

Call Stack in Programming

DFS recursion uses the program's call stack to remember nodes to visit next.

Knowing how DFS uses the call stack clarifies recursion limits and helps design iterative DFS.

Human Problem Solving

DFS mimics how people explore options deeply before backtracking to try alternatives.

Recognizing this connection helps understand DFS as a natural search strategy, not just a technical trick.

Common Pitfalls

#1 Infinite loop by revisiting nodes in cyclic graphs.

Wrong approach:

def dfs(node, graph):
print(node)
for neighbor in graph[node]:
dfs(neighbor, graph)

Correct approach:

visited = set()
def dfs(node, graph):
if node in visited:
return
visited.add(node)
print(node)
for neighbor in graph[node]:
dfs(neighbor, graph)

Root cause:

Not tracking visited nodes causes repeated visits and infinite recursion.

#2 Stack overflow due to deep recursion in large graphs.

Wrong approach:

def dfs(node, graph):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor, graph)

# Called on very deep graph

Correct approach:

def dfs_iterative(start, graph):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])

Root cause:

Recursive calls exceed call stack limit; iterative approach avoids this.

#3 Assuming DFS finds shortest path.

Wrong approach:

def dfs_path(start, target, graph, path=[]):
path = path + [start]
if start == target:
return path
for neighbor in graph[start]:
if neighbor not in path:
newpath = dfs_path(neighbor, target, graph, path)
if newpath:
return newpath
return None

# Using this to find shortest path

Correct approach:

Use BFS for shortest path:
from collections import deque

def bfs_shortest_path(start, target, graph):
visited = set()
queue = deque([[start]])
while queue:
path = queue.popleft()
node = path[-1]
if node == target:
return path
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
new_path = list(path)
new_path.append(neighbor)
queue.append(new_path)

Root cause:

DFS explores deeply and may find longer paths first; BFS explores level-wise guaranteeing shortest path.

Key Takeaways

Depth First Search (DFS) explores graphs by going as deep as possible before backtracking, ensuring all reachable nodes are visited.

DFS can be implemented using recursion or an explicit stack, with careful tracking of visited nodes to avoid infinite loops.

DFS does not guarantee shortest paths; for shortest paths, Breadth First Search (BFS) or other algorithms are better choices.

Understanding DFS's mechanism and limitations prepares you for advanced graph algorithms and real-world problem solving.

Advanced DFS techniques handle cycles, connected components, and large graphs by adapting recursion depth or using iterative methods.

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