Topological Sort Using DFS in DSA Rust - Execution Trace

Concept Flow - Topological Sort Using DFS

Start with all nodes

↓

Pick unvisited node

↓

DFS: Mark node visited

↓

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 topological order

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

Execution Sample

DSA Rust

fn dfs(node: usize, graph: &Vec<Vec<usize>>, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            dfs(neighbor, graph, visited, stack);
        }
    }
    stack.push(node);
}

This code runs DFS on a node, visits all neighbors recursively, then pushes the node to stack for topological sorting.

Execution Table

Step	Operation	Current Node	Visited Set	Stack	Visual State
1	Start DFS at node 0	0	[0]	[]	Graph nodes: 0->1,2; 1->3; 2->3; 3->none
2	Visit neighbor 1 of node 0	1	[0,1]	[]	Visiting node 1 from 0
3	Visit neighbor 3 of node 1	3	[0,1,3]	[]	Visiting node 3 from 1
4	Node 3 has no neighbors, push 3	3	[0,1,3]	[3]	Stack after pushing 3
5	Back to node 1, all neighbors visited, push 1	1	[0,1,3]	[3,1]	Stack after pushing 1
6	Back to node 0, visit neighbor 2	2	[0,1,2,3]	[3,1]	Visiting node 2 from 0
7	Visit neighbor 3 of node 2 (already visited)	3	[0,1,2,3]	[3,1]	Skip node 3, already visited
8	Node 2 all neighbors visited, push 2	2	[0,1,2,3]	[3,1,2]	Stack after pushing 2
9	Back to node 0, all neighbors visited, push 0	0	[0,1,2,3]	[3,1,2,0]	Stack after pushing 0
10	All nodes visited, pop stack for order	-	[0,1,2,3]	[3,1,2,0]	Topological order: 0->2->1->3

💡 All nodes visited and pushed to stack; stack popped for topological order.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9	Final
visited	[false,false,false,false]	[true,false,false,false]	[true,true,false,false]	[true,true,false,true]	[true,true,false,true]	[true,true,false,true]	[true,true,true,true]	[true,true,true,true]	[true,true,true,true]	[true,true,true,true]	[true,true,true,true]
stack	[]	[]	[]	[3]	[3,1]	[3,1]	[3,1]	[3,1,2]	[3,1,2]	[3,1,2,0]	[3,1,2,0]
current_node	-	0	1	3	3	1	2	3	2	0	-

Key Moments - 3 Insights

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

Because in the execution_table rows 4, 5, 8, and 9, nodes are pushed after all neighbors are visited, ensuring dependencies come before the node in the final order.

Why do we skip visiting a neighbor if it is already marked visited?

As shown in step 7, visiting an already visited node is skipped to avoid infinite loops and repeated work, ensuring each node is processed once.

How does popping the stack give the correct topological order?

The stack stores nodes after their dependencies; popping reverses this order, as seen in step 10, producing a valid topological order.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the content of the stack?

A [1]

B []

C [3]

D [3,1]

💡 Hint

Check the 'Stack' column in execution_table row for step 4.

At which step does the node 2 get pushed to the stack?

A Step 8

B Step 7

C Step 6

D Step 9

💡 Hint

Look at the 'Operation' and 'Stack' columns in execution_table rows around step 8.

If node 3 was not visited before step 7, what would happen in the execution_table?

A Node 3 would be skipped at step 7

B DFS would visit node 3 again at step 7

C Node 3 would be pushed to stack at step 6

D The stack would be empty

💡 Hint

Refer to the 'Visited Set' and 'Operation' columns at step 7.

Concept Snapshot

Topological Sort Using DFS:
- Visit each node once using DFS
- Recursively visit all neighbors first
- After neighbors, push node to stack
- Pop stack for topological order
- Ensures dependencies come before dependents

Full Transcript

Topological Sort using DFS starts by picking unvisited nodes and exploring their neighbors recursively. Each node is marked visited to avoid repeats. After visiting all neighbors, the node is pushed onto a stack. Once all nodes are processed, popping the stack gives the topological order. This ensures nodes appear after their dependencies. The execution table shows step-by-step how nodes are visited, neighbors explored, and nodes pushed to the stack. The variable tracker records visited nodes and stack contents after each step. Key moments clarify why nodes are pushed after neighbors and why revisiting visited nodes is skipped. The visual quiz tests understanding of stack contents and visit order at specific steps.

Practice

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

easy

A. To detect cycles in an undirected graph

B. To find the shortest path between two nodes

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

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 first.

2. Step 2: Relation to dependencies

   In Topological Sort, DFS ensures nodes are added after all their dependencies (incoming edges) are processed.

3. Final Answer:

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

4. Quick Check:

   DFS orders nodes respecting dependencies [OK]

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

Common Mistakes:

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

2. Which of the following Rust code snippets correctly declares a recursive DFS function for topological sort?

easy

A. fn dfs(node: usize, graph: &Vec, visited: Vec<bool>, stack: &mut Vec<usize>) { /* body */ }

B. fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, stack: &mut Vec<usize>) { /* body */ }

C. fn dfs(node: &usize, graph: &Vec<usize>, visited: &Vec<bool>, stack: &Vec<usize>) { /* body */ }

D. fn dfs(node: usize, graph: Vec, visited: Vec<bool>, stack: Vec<usize>) { /* body */ }

Solution

1. Step 1: Check parameter passing for DFS

   Graph and visited must be passed by reference to avoid copying; stack must be mutable reference to push nodes.

2. Step 2: Analyze options

   fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, stack: &mut Vec<usize>) { /* body */ } passes graph and visited by reference and stack as mutable reference, correct for DFS recursion.

3. Final Answer:

   fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, stack: &mut Vec<usize>) { /* body */ } -> Option B

4. Quick Check:

   Correct references and mutability in parameters [OK]

Hint: Pass graph and visited by reference, stack as mutable reference [OK]

Common Mistakes:

• Passing graph or visited by value causing copies
• Not using mutable reference for stack
• Incorrect types for graph adjacency list

3. Given the following graph edges: 0->1, 0->2, 1->3, 2->3, what is the topological order output by DFS-based topological sort starting from node 0?

fn main() {
    let graph = vec![
        vec![1, 2],
        vec![3],
        vec![3],
        vec![],
    ];
    let mut visited = vec![false; 4];
    let mut stack = Vec::new();
    dfs(0, &graph, &mut visited, &mut stack);
    while let Some(node) = stack.pop() {
        print!("{} ", node);
    }
}

fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
    if visited[node] { return; }
    visited[node] = true;
    for &neighbor in &graph[node] {
        dfs(neighbor, graph, visited, stack);
    }
    stack.push(node);
}

medium

A. 0 2 1 3

B. 3 1 2 0

C. 0 1 2 3

D. 3 2 1 0

Solution

1. Step 1: Trace DFS calls and stack pushes

   DFS starts at 0, visits 1, then 3 (push 3), back to 1 (push 1), then visits 2, then 3 (already visited), push 2, finally push 0.

2. Step 2: Stack content and output order

   Stack after DFS: [3,1,2,0]. Popping gives 0 then 2 then 1 then 3, printing "0 2 1 3".

3. Final Answer:

   0 2 1 3 -> Option A

4. Quick Check:

   DFS post-order stack reversed = topological order [OK]

Hint: Stack push after recursion; pop reverses order [OK]

Common Mistakes:

• Printing stack before reversing
• Not marking visited nodes
• Confusing order of push and pop

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

fn dfs(node: usize, graph: &Vec, visited: &mut Vec<bool>, stack: &mut Vec<usize>) {
    visited[node] = true;
    for &neighbor in &graph[node] {
        if !visited[neighbor] {
            dfs(neighbor, graph, visited, stack);
        }
    }
    stack.push(node);
}

fn main() {
    let graph = vec![vec![1], vec![2], vec![0]];
    let mut visited = vec![false; 3];
    let mut stack = Vec::new();
    for i in 0..3 {
        if !visited[i] {
            dfs(i, &graph, &mut visited, &mut stack);
        }
    }
    while let Some(node) = stack.pop() {
        print!("{} ", node);
    }
}

medium

A. DFS does not mark nodes as visited

B. Visited vector is not initialized correctly

C. Stack is not cleared before use

D. The graph contains a cycle, so topological sort is invalid

Solution

1. Step 1: Analyze graph edges

   Edges: 0->1, 1->2, 2->0 form a cycle.

2. Step 2: Understand topological sort limitation

   Topological sort requires DAG (no cycles). Cycle presence makes ordering impossible.

3. Final Answer:

   The graph contains a cycle, so topological sort is invalid -> Option D

4. Quick Check:

   Cycle in graph prevents valid topological order [OK]

Hint: Check for cycles before topological sort [OK]

Common Mistakes:

• Ignoring cycles in input graph
• Assuming topological sort works on cyclic graphs
• Not detecting cycles before sorting

5. You have a project with tasks and dependencies: Task 5 depends on 2 and 0, Task 4 depends on 0 and 1, Task 2 depends on 3, Task 3 depends on 1. Using DFS-based topological sort, which of these is a valid order to complete all tasks? Tasks: 0,1,2,3,4,5 Dependencies: - 5 -> 2,0 - 4 -> 0,1 - 2 -> 3 - 3 -> 1 Options: A) 1 3 0 2 4 5 B) 1 2 3 0 4 5 C) 0 1 2 3 4 5 D) 3 1 0 2 4 5

hard

A. 1 3 0 2 4 5

B. 1 2 3 0 4 5

C. 0 1 2 3 4 5

D. 3 1 0 2 4 5

Solution

1. Step 1: Analyze dependencies order

   Task 5 after 2 and 0; 4 after 0 and 1; 2 after 3; 3 after 1.

2. Step 2: Validate each option

   1 3 0 2 4 5 respects all: 1 before 3, 3 before 2, 0 before 4 and 5, 2 and 0 before 5, 1 and 0 before 4.

3. Final Answer:

   1 3 0 2 4 5 -> Option A

4. Quick Check:

   All dependencies precede dependent tasks [OK]

Hint: Check all dependencies appear before dependent tasks [OK]

Common Mistakes:

• Ignoring order of dependencies
• Placing dependent tasks before prerequisites
• Confusing task numbers and dependencies