DFS Depth First Search on Graph in DSA Python - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does DFS stand for in graph traversal?

DFS stands for Depth First Search, a method to explore graph nodes by going as deep as possible before backtracking.

beginner

In DFS, what data structure is commonly used to keep track of nodes to visit next?

A stack is commonly used in DFS to keep track of nodes to visit next, either explicitly or via recursion call stack.

intermediate

What is the main difference between DFS and BFS in graph traversal?

DFS explores as far as possible along each branch before backtracking, while BFS explores all neighbors at the current depth before moving deeper.

beginner

Why do we mark nodes as visited in DFS?

Marking nodes as visited prevents revisiting the same node, avoiding infinite loops and repeated work.

intermediate

What is the time complexity of DFS on a graph with V vertices and E edges?

The time complexity of DFS is O(V + E), because it visits every vertex and edge once.

Which data structure does DFS use implicitly when implemented recursively?

A Stack

B Queue

C Heap

D Hash Table

DFS uses the call stack implicitly when implemented recursively, which behaves like a stack.

What happens if you don't mark nodes as visited in DFS on a graph with cycles?

A DFS will only visit nodes once

B DFS will skip some nodes

C DFS will convert the graph to a tree

D DFS will run infinitely or revisit nodes repeatedly

Without marking visited nodes, DFS can get stuck in cycles and run infinitely or revisit nodes multiple times.

In DFS, which order are nodes visited?

A Go deep into one branch before exploring others

B Visit all neighbors before going deeper

C Visit nodes randomly

D Visit nodes in increasing order of value

DFS explores as deep as possible along one branch before backtracking to explore others.

What is the space complexity of DFS in the worst case for a graph with V vertices?

A O(log V)

B O(V)

C O(E)

D O(1)

DFS can use O(V) space in the worst case due to the recursion stack or explicit stack storing nodes.

Which of these is NOT a typical use case of DFS?

A Finding connected components

B Topological sorting

C Finding shortest path in unweighted graph

D Detecting cycles

Finding shortest path in unweighted graphs is better done with BFS, not DFS.

Explain how DFS works on a graph starting from a given node.

Think about going deep into neighbors before moving sideways.

Describe why marking nodes as visited is important in DFS and what could happen if you don't.

Imagine walking in a maze without marking where you have been.

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