Topological Sort Using DFS in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Topological Sort on a Simple DAG

What is the output of the following topological sort using DFS on the given graph?

DSA Python

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

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
visited = set()
stack = []
for node in graph:
    if node not in visited:
        dfs(node, graph, visited, stack)

stack.reverse()
print(' -> '.join(stack) + ' -> null')

A A -> C -> B -> D -> null

B A -> B -> C -> D -> null

C D -> B -> C -> A -> null

D A -> B -> D -> C -> null

💡 Hint

Remember that in DFS-based topological sort, nodes are added to the stack after visiting all their neighbors.

The DFS visits nodes starting from 'A'. It explores 'B' and then 'D', then backtracks to explore 'C' and 'D' (already visited). The stack after DFS is ['D', 'B', 'C', 'A'], reversing it gives ['A', 'B', 'C', 'D'] which is the correct topological order.

🧠 Conceptual

intermediate

Detecting Cycles in DFS for Topological Sort

Why is it important to detect cycles when performing a topological sort using DFS?

A Because cycles allow multiple valid topological orders, so detection is optional.

B Because cycles speed up the DFS traversal and improve performance.

C Because cycles help in finding the shortest path in the graph.

D Because topological sort only works on graphs without cycles (DAGs), cycles make sorting impossible.

💡 Hint

Think about what a cycle means for ordering tasks.

Topological sort requires a Directed Acyclic Graph (DAG). If there is a cycle, no linear ordering exists because tasks depend on each other in a loop, making sorting impossible.

❓ Predict Output

advanced

Output of Topological Sort with Multiple Independent Chains

What is the output of the topological sort using DFS on this graph with two independent chains?

DSA Python

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

graph = {
    'X': ['Y'],
    'Y': [],
    'A': ['B'],
    'B': []
}
visited = set()
stack = []
for node in graph:
    if node not in visited:
        dfs(node, graph, visited, stack)

stack.reverse()
print(' -> '.join(stack) + ' -> null')

A A -> B -> X -> Y -> null

B Y -> X -> B -> A -> null

C A -> X -> B -> Y -> null

D X -> Y -> A -> B -> null

💡 Hint

The order depends on the order nodes are visited in the for loop and DFS completion.

The for loop visits 'X' first, then 'Y', then 'A', then 'B'. DFS on 'X' visits 'Y', stack after is ['Y', 'X']. Then DFS on 'A' visits 'B', stack after is ['Y', 'X', 'B', 'A']. Reversing gives ['A', 'B', 'X', 'Y'].

🔧 Debug

advanced

Identify the Bug in DFS Topological Sort Implementation

What error will this code produce when running topological sort using DFS?

DSA Python

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

graph = {
    'A': ['B'],
    'B': ['C'],
    'C': []
}
visited = set()
stack = []
for node in ['A', 'B', 'C', 'D']:
    if node not in visited:
        dfs(node, graph, visited, stack)

stack.reverse()
print(' -> '.join(stack) + ' -> null')

A KeyError: 'D'

B IndexError: list index out of range

C No error, prints: A -> B -> C -> null

D TypeError: unhashable type

💡 Hint

Check what happens when the code tries to access graph[node] for a node not in the graph.

The for loop includes 'D' which is not a key in the graph dictionary. Accessing graph['D'] causes a KeyError.

🚀 Application

expert

Number of Valid Topological Orders in a DAG

Given a DAG with edges: 1->2, 1->3, 3->4, 2->4, how many valid topological orders exist?

A 3

B 4

C 2

D 1

💡 Hint

Try listing all valid orders respecting the edges.

The graph edges impose constraints: 1 before 2 and 3, and both 2 and 3 before 4. Possible orders are:
1,2,3,4
1,3,2,4
So total 2 unique valid orders.

Practice

1. What is the main purpose of using DFS in Topological Sort on a directed graph?

easy

A. To visit nodes in a way that all dependencies come before the node itself

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To count the number of connected components

Solution

1. Step 1: Understand DFS role in Topological Sort

   DFS visits nodes deeply, ensuring all nodes reachable from a node are visited before the node itself.

2. Step 2: Relate DFS order to dependencies

   In Topological Sort, this means all dependencies (nodes with edges to current node) are processed before the node, preserving order.

3. Final Answer:

   To visit nodes in a way that all dependencies come before the node itself -> Option A

4. Quick Check:

   DFS ensures dependency order in Topological Sort [OK]

Hint: DFS visits dependencies before the node itself [OK]

Common Mistakes:

• Confusing DFS with BFS for topological order
• Thinking DFS finds shortest paths here
• Mixing cycle detection with topological sorting

2. Which of the following is the correct way to mark a node as visited in a DFS-based topological sort in Python?

easy

A. visited.add(node)

B. visited[node] == True

C. visited[node] = True

D. visited.append(node)

Solution

1. Step 1: Understand visited data structure type

   Usually, visited is a list or dictionary indexed by node, so marking visited means assigning True to that index.

2. Step 2: Identify correct syntax for assignment

   Using visited[node] = True correctly marks the node as visited. Using '==' is a comparison, not assignment.

3. Final Answer:

   visited[node] = True -> Option C

4. Quick Check:

   Assign True to visited[node] to mark visited [OK]

Hint: Use assignment (=), not comparison (==), to mark visited [OK]

Common Mistakes:

• Using '==' instead of '=' for assignment
• Using visited.append(node) when visited is a dict/list
• Using visited.add(node) when visited is not a set

3. What is the output of the following code snippet for topological sort using DFS?

graph = {0: [1, 2], 1: [2], 2: []}
visited = [False, False, False]
stack = []
def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)
    stack.append(node)

for v in range(3):
    if not visited[v]:
        dfs(v)
print(stack[::-1])

medium

A. [0, 1, 2]

B. [2, 1, 0]

C. [1, 0, 2]

D. [2, 0, 1]

Solution

1. Step 1: Trace DFS calls and stack appends

   Start with node 0: visit 0, then neighbors 1 and 2. DFS(1) visits 1, then 2. DFS(2) visits 2, appends 2. Then append 1, then append 0.

2. Step 2: Reverse stack to get topological order

   Stack after DFS: [2, 1, 0]. Reversing gives [0, 1, 2].

3. Final Answer:

   [0, 1, 2] -> Option A

4. Quick Check:

   Stack reversed gives correct topological order [OK]

Hint: Reverse stack after DFS to get topological order [OK]

Common Mistakes:

• Not reversing the stack before printing
• Appending nodes before recursive DFS calls
• Confusing order of neighbors visited

4. Identify the error in this DFS-based topological sort code snippet:

def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if visited[neighbor]:
            dfs(neighbor)
    stack.append(node)

medium

A. DFS should not append nodes to stack

B. Stack should be cleared before DFS

C. Visited should be a set, not a list

D. The condition should be 'if not visited[neighbor]' before calling dfs

Solution

1. Step 1: Analyze the if condition in DFS

   The code calls dfs(neighbor) only if visited[neighbor] is True, which means neighbor was already visited. This causes repeated visits or infinite recursion.

2. Step 2: Correct the condition to avoid revisiting

   The condition should be 'if not visited[neighbor]' to visit unvisited neighbors only.

3. Final Answer:

   The condition should be 'if not visited[neighbor]' before calling dfs -> Option D

4. Quick Check:

   Visit neighbors only if not visited [OK]

Hint: Call dfs only on unvisited neighbors [OK]

Common Mistakes:

• Calling dfs on already visited nodes
• Not marking nodes visited before recursion
• Appending nodes to stack too early

5. Given a directed acyclic graph with edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1, which of the following is a valid topological order using DFS-based topological sort?

hard

A. [1, 3, 2, 4, 5, 0]

B. [5, 4, 2, 3, 1, 0]

C. [0, 1, 2, 3, 4, 5]

D. [5, 2, 3, 1, 0, 4]

Solution

1. Step 1: Understand dependencies from edges

   Edges mean 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. So 5 and 4 come before 2,3,1,0.

2. Step 2: Check each option for order validity

   [5, 4, 2, 3, 1, 0] respects all edges: 5 before 2 and 0, 4 before 0 and 1, 2 before 3, 3 before 1. Others violate these orders.

3. Final Answer:

   [5, 4, 2, 3, 1, 0] -> Option B

4. Quick Check:

   All edges respected in order [OK]

Hint: Check all edges respected in order for valid topological sort [OK]

Common Mistakes:

• Ignoring edge directions in order
• Assuming any order of nodes is valid
• Not verifying all dependencies before nodes