Bird
Raised Fist0

Examine the following buggy iterative DFS code for finding all paths from source to target in a DAG:

medium🐞 Bug Identification Q14 of Q15
Topological Sort - All Paths From Source to Target (DAG)
Examine the following buggy iterative DFS code for finding all paths from source to target in a DAG:
def allPathsSourceTarget(graph):
    target = len(graph) - 1
    res = []
    stack = [(0, [0])]

    while stack:
        node, path = stack.pop()
        if node == target:
            res.append(path)  # Bug here
        else:
            for nei in graph[node]:
                stack.append((nei, path + [nei]))
    return res
What is the bug in this code?
ANot backtracking path after recursion leads to corrupted paths
BNot checking for cycles can cause infinite loops
CStack initialization missing the source node
DAppending path directly without copying causes all results to reference the same list
Step-by-Step Solution
  1. Step 1: Understand path storage and cycle detection

    The code does not check for cycles, which can cause infinite loops if the graph contains cycles.
  2. Step 2: Consequence of bug

    Without cycle detection, the DFS can revisit nodes indefinitely, causing infinite loops.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Cycle detection is necessary in graphs that may contain cycles to prevent infinite loops [OK]
Quick Trick: Add cycle detection or visited set to prevent infinite loops [OK]
Common Mistakes:
MISTAKES
  • Assuming DAG always; ignoring cycles
  • Confusing path copying with cycle detection
Trap Explanation:
PITFALL
  • Appending path directly is safe here because path + [nei] creates new lists; the real bug is missing cycle detection.
Interviewer Note:
CONTEXT
  • Tests candidate's understanding of cycle detection necessity in DFS for graphs that may have cycles.
Master "All Paths From Source to Target (DAG)" in Topological Sort

3 interactive learning modes - each teaches the same concept differently

Want More Practice?

15+ quiz questions · All difficulty levels · Free

Free Signup - Practice All Questions
More Topological Sort Quizzes