DFS traversal and applications in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to start a DFS traversal from the given node.

Data Structures Theory

def dfs(node, visited):
    if node is None or node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs([1], visited)

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

Anode

BNone

Cvisited

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Calling dfs on the current node again causes infinite recursion.

Passing visited instead of the next node.

In DFS, we recursively visit each neighbor of the current node. So, the recursive call should be on neighbor.

2fill in blank

medium

Complete the code to mark a node as visited in DFS.

Data Structures Theory

def dfs(node, visited):
    if node is None or node in visited:
        return
    [1].add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

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

Aneighbor

Bnode

Cvisited

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Adding the neighbor instead of the current node.

Trying to add to the node instead of the visited set.

We add the current node to the visited set to mark it as visited and avoid revisiting it.

3fill in blank

hard

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

Data Structures Theory

def dfs(node, visited):
    if node is None or [1]:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited)

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

Anode in visited

Bnode not in visited

Cneighbor in visited

Dneighbor not in visited

Attempts:

3 left

💡 Hint

Common Mistakes

Checking if node is not in visited causes infinite recursion.

Checking neighbors instead of the current node.

The condition should check if the current node is already in visited to stop revisiting it.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension that maps nodes to their depth in DFS.

Data Structures Theory

def dfs_depth(node, depth, depths, visited):
    if node is None or node in visited:
        return
    visited.add(node)
    depths[node] = depth
    for neighbor in node.neighbors:
        dfs_depth(neighbor, depth [1] 1, depths, visited)

result = {node: depths[node] for node in depths if depths[node] [2] 2}

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

A+

B-

C>

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction instead of addition for depth.

Using wrong comparison operator for filtering.

We increase depth by 1 when going deeper in DFS, so use +. To filter nodes deeper than 2, use >.

5fill in blank

hard

Fill all three blanks to create a dictionary comprehension that maps nodes to their neighbors if the neighbor is unvisited.

Data Structures Theory

def dfs_neighbors(node, visited):
    return {neighbor: node for neighbor in node.neighbors if neighbor not in [1]

visited = set()
result = dfs_neighbors([2], visited)
visited.add([3])

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

Avisited

Bnode

Cneighbor

DNone

Attempts:

3 left

💡 Hint

Common Mistakes

Using neighbor instead of visited for the check.

Adding neighbor instead of node to visited.

The comprehension checks neighbors not in visited. We call the function on node and add node to visited.

Practice

1. What is the main idea behind Depth-First Search (DFS) traversal in a graph?

easy

A. Visit all neighbors of a node before moving deeper

B. Explore as far as possible along each branch before backtracking

C. Visit nodes in order of their distance from the start node

D. Randomly visit nodes without any specific order

Solution

1. Step 1: Understand DFS traversal approach

   DFS explores nodes by going deep into one branch before checking others.

2. Step 2: Compare with other traversal methods

   BFS visits neighbors first, but DFS goes deep first, then backtracks.

3. Final Answer:

   Explore as far as possible along each branch before backtracking -> Option B

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 all neighbors first
• Assuming DFS visits nodes by distance

2. Which of the following is the correct way to mark a node as visited in DFS pseudocode?

easy

A. visited[node] = True

B. visited[node] = False

C. visited = node

D. visited.append(node)

Solution

1. Step 1: Understand visited marking in DFS

   Nodes are marked visited by setting their status to True to avoid revisiting.

2. Step 2: Analyze options

   Setting visited[node] = True correctly marks the node; others are incorrect or incomplete.

3. Final Answer:

   visited[node] = True -> Option A

4. Quick Check:

   Mark visited nodes as True [OK]

Hint: Visited nodes are marked True to avoid loops [OK]

Common Mistakes:

• Marking visited as False instead of True
• Using append instead of assignment
• Assigning visited to node directly

3. Consider the following graph edges: 1->2, 1->3, 2->4, 3->4. Starting DFS from node 1, which is the order of nodes visited?

medium

A. [1, 4, 2, 3]

B. [1, 3, 4, 2]

C. [1, 2, 3, 4]

D. [1, 2, 4, 3]

Solution

1. Step 1: Start DFS at node 1 and explore neighbors

   From 1, DFS visits 2 first (assuming adjacency order), then explores 2's neighbor 4.

2. Step 2: Backtrack and visit remaining neighbors

   After finishing 2 and 4, DFS backtracks to 1 and visits 3, then 3's neighbor 4 is already visited.

3. Final Answer:

   [1, 2, 4, 3] -> Option D

4. Quick Check:

   DFS order = deep first, backtrack [OK]

Hint: Follow neighbors deeply before backtracking [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Visiting node 4 twice
• Confusing BFS order with DFS

4. In a DFS implementation, what is the likely cause if the traversal gets stuck in an infinite loop?

medium

A. Starting from a disconnected node

B. Using a queue instead of a stack

C. Not marking nodes as visited

D. Graph has no edges

Solution

1. Step 1: Identify cause of infinite loop in DFS

   If nodes are not marked visited, DFS revisits the same nodes repeatedly causing infinite loops.

2. Step 2: Analyze other options

   Using a queue changes traversal type but doesn't cause infinite loops; disconnected nodes or no edges don't cause loops.

3. Final Answer:

   Not marking nodes as visited -> Option C

4. Quick Check:

   Missing visited marks cause loops [OK]

Hint: Always mark visited nodes to prevent loops [OK]

Common Mistakes:

• Blaming data structure choice for loops
• Ignoring visited marking importance
• Assuming disconnected nodes cause loops

5. You want to use DFS to detect if a directed graph has a cycle. Which approach correctly applies DFS for this task?

hard

A. Use DFS with a recursion stack to track nodes currently in the path

B. Use DFS and mark all nodes as visited once explored, ignoring recursion stack

C. Use BFS instead of DFS to detect cycles

D. Count edges and nodes; if edges > nodes, cycle exists

Solution

1. Step 1: Understand cycle detection in directed graphs

   DFS with a recursion stack tracks nodes in the current path to detect back edges indicating cycles.

2. Step 2: Evaluate other options

   Marking visited alone misses cycles; BFS is not ideal for cycle detection; counting edges vs nodes is insufficient.

3. Final Answer:

   Use DFS with a recursion stack to track nodes currently in the path -> Option A

4. Quick Check:

   Recursion stack in DFS detects cycles [OK]

Hint: Track recursion stack in DFS to find cycles [OK]

Common Mistakes:

• Ignoring recursion stack in cycle detection
• Using BFS for cycle detection in directed graphs
• Relying on edge/node count alone