DFS Depth First Search on Graph in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start DFS from the given node.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Cvisited

Dgraph

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' instead of 'neighbor' in the recursive call.

Passing 'visited' incorrectly.

Calling dfs with the whole graph instead of a node.

The DFS function should recursively call itself on each neighbor of the current node.

2fill in blank

medium

Complete the code to initialize the visited set before starting DFS.

DSA Python

def dfs_start(graph, start_node):
    visited = [1]
    dfs(graph, start_node, visited)
    return visited

Drag options to blanks, or click blank then click option'

A[]

B{}

CNone

Dset()

Attempts:

3 left

💡 Hint

Common Mistakes

Using a list instead of a set for visited nodes.

Using an empty dictionary {} which is not suitable here.

Using None which causes errors.

A set is used to keep track of visited nodes for efficient membership checking.

3fill in blank

hard

Fix the error in the DFS function to avoid revisiting nodes.

DSA Python

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

Drag options to blanks, or click blank then click option'

Aneighbor

Bnode

Cgraph

Dvisited

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if neighbor is in visited instead of node.

Checking if graph is in visited.

Checking if visited is in visited (nonsense).

We check if the current node is already visited to avoid infinite loops.

4fill in blank

hard

Fill in the blank to create a DFS that collects nodes in order visited.

DSA Python

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

result = []
visited = set()
dfs_collect(graph, 'A', visited, result)
print(result)

Drag options to blanks, or click blank then click option'

Ainsert

Badd

Cappend

Dextend

Attempts:

3 left

💡 Hint

Common Mistakes

Using add which is for sets, not lists.

Using insert without index which causes errors.

Using extend which expects an iterable.

We use append to add nodes to the result list in the order they are visited.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps nodes to their visit order index.

DSA Python

def dfs_order(graph, start):
    visited = set()
    order = []
    def dfs(node):
        if node not in visited:
            visited.add(node)
            order.[1](node)
            for neighbor in graph[node]:
                dfs(neighbor)
    dfs(start)
    return { [3]: [2] for [2], node in enumerate(order)}

Drag options to blanks, or click blank then click option'

Aappend

Bnode

Ci

Dorder

Attempts:

3 left

💡 Hint

Common Mistakes

Using add instead of append for the list.

Swapping keys and values in the dictionary comprehension.

Using wrong variable names in the comprehension.

We append nodes to order, then create a dictionary mapping each node to its index i.

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