Topological Sort Using DFS in DSA Python - Execution Trace

Concept Flow - Topological Sort Using DFS

Start with all nodes

↓

Pick unvisited node

↓

DFS: Visit node

↓

For each neighbor

↓

If neighbor unvisited

↓

Recursive DFS on neighbor

↓

After all neighbors visited

↓

Add node to stack

↓

Repeat until all nodes visited

↓

Pop all nodes from stack for order

Start DFS from unvisited nodes, visit neighbors recursively, then add nodes to stack. Finally, pop stack for topological order.

Execution Sample

DSA Python

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

Perform DFS on a node, recursively visit neighbors, then add node to stack for topological order.

Execution Table

Step	Operation	Current Node	Visited Set	Stack	Visual State
1	Start DFS at node 5	5	{}	[]	Graph: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1 Visited: none Stack: empty
2	Visit node 5	5	{5}	[]	Visited 5
3	Go to neighbor 2	2	{5}	[]	Visiting neighbor 2 from 5
4	Visit node 2	2	{2,5}	[]	Visited 2
5	Go to neighbor 3	3	{2,5}	[]	Visiting neighbor 3 from 2
6	Visit node 3	3	{2,3,5}	[]	Visited 3
7	Go to neighbor 1	1	{2,3,5}	[]	Visiting neighbor 1 from 3
8	Visit node 1	1	{1,2,3,5}	[]	Visited 1
9	Node 1 has no neighbors	1	{1,2,3,5}	[1]	Add 1 to stack
10	Back to node 3	3	{1,2,3,5}	[1,3]	Add 3 to stack
11	Back to node 2	2	{1,2,3,5}	[1,3,2]	Add 2 to stack
12	Back to node 5	5	{1,2,3,5}	[1,3,2]	Continue neighbors of 5
13	Go to neighbor 0	0	{1,2,3,5}	[1,3,2]	Visiting neighbor 0 from 5
14	Visit node 0	0	{0,1,2,3,5}	[1,3,2]	Visited 0
15	Node 0 has no neighbors	0	{0,1,2,3,5}	[1,3,2,0]	Add 0 to stack
16	Back to node 5	5	{0,1,2,3,5}	[1,3,2,0,5]	Add 5 to stack
17	Start DFS at node 4	4	{0,1,2,3,5}	[1,3,2,0,5]	Node 4 unvisited, start DFS
18	Visit node 4	4	{0,1,2,3,4,5}	[1,3,2,0,5]	Visited 4
19	Go to neighbor 0	0	{0,1,2,3,4,5}	[1,3,2,0,5]	Neighbor 0 already visited
20	Go to neighbor 1	1	{0,1,2,3,4,5}	[1,3,2,0,5]	Neighbor 1 already visited
21	Node 4 neighbors done	4	{0,1,2,3,4,5}	[1,3,2,0,5,4]	Add 4 to stack
22	All nodes visited	-	{0,1,2,3,4,5}	[1,3,2,0,5,4]	DFS complete
23	Pop stack for order	-	-	-	Topological order: 4 -> 5 -> 0 -> 2 -> 3 -> 1

💡 All nodes visited, stack contains nodes in reverse topological order

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 9	After Step 11	After Step 15	After Step 16	After Step 21	Final
visited	{}	{5}	{2,5}	{2,3,5}	{1,2,3,5}	{1,2,3,5}	{0,1,2,3,5}	{0,1,2,3,5}	{0,1,2,3,4,5}	{0,1,2,3,4,5}
stack	[]	[]	[]	[]	[1]	[1,3,2]	[1,3,2,0]	[1,3,2,0,5]	[1,3,2,0,5,4]	[1,3,2,0,5,4]

Key Moments - 3 Insights

Why do we add the node to the stack only after visiting all its neighbors?

Because topological order requires that all dependencies (neighbors) come before the node. Adding after neighbors ensures correct order, as shown in steps 9, 10, 11 where nodes are added after their neighbors.

Why do we start DFS from unvisited nodes only?

To avoid revisiting nodes and infinite loops. The visited set (tracked in variable_tracker) ensures each node is processed once, as seen in steps 17-21 where node 4 is visited after others.

How does the stack represent the topological order?

The stack stores nodes in reverse order of completion. Popping the stack (step 23) gives the correct topological order, because nodes are pushed after all their dependencies.

Visual Quiz - 3 Questions

Look at the execution_table at step 9, what is the stack content?

A [3, 1]

B []

C [1]

D [2, 3, 1]

💡 Hint

Check the 'Stack' column at step 9 in execution_table

At which step does node 4 get added to the stack?

A Step 21

B Step 16

C Step 22

D Step 23

💡 Hint

Look for 'Add 4 to stack' in the 'Operation' column of execution_table

If node 3 had an additional neighbor 6 unvisited, what would change in the execution_table?

A Node 6 would never be visited

B DFS would visit node 6 before adding 3 to stack

C Node 3 would be added to stack immediately

D Stack order would remain the same

💡 Hint

Recall DFS visits all neighbors before adding current node to stack

Concept Snapshot

Topological Sort Using DFS:
- Use DFS to visit nodes
- Mark nodes visited to avoid repeats
- Recursively visit all neighbors first
- Add node to stack after neighbors
- Pop stack for topological order
- Works only on Directed Acyclic Graphs (DAGs)

Full Transcript

Topological Sort using DFS starts by picking unvisited nodes and performing a depth-first search. Each node is marked visited when first seen. The algorithm recursively visits all neighbors before adding the current node to a stack. This ensures dependencies come before dependents. After all nodes are visited, popping the stack gives the topological order. The execution table shows step-by-step how nodes are visited, neighbors explored, and nodes added to the stack. The variable tracker records the visited set and stack content after key steps. Key moments clarify why nodes are added after neighbors and why unvisited nodes start DFS. The visual quiz tests understanding of stack content and DFS order. This method works only on directed acyclic graphs to produce a valid order.

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