Topological Sort Using DFS in DSA Rust

Mental Model

We visit each task and all tasks that depend on it first, then add the task to the order. This way, dependencies come before the tasks that need them.

Analogy: Imagine you have to finish homework problems, but some problems need answers from others first. You solve the ones without dependencies first, then the ones that depend on them, like stacking books in order.

Graph:
A -> B -> C
↑         ↓
D ---------

Start DFS at nodes with no incoming edges.
Stack stores tasks after visiting dependents.
Final order is stack reversed.

Dry Run Walkthrough

Input: Graph edges: A->B, B->C, D->A, D->C

Goal: Find an order to complete tasks so all dependencies come before dependent tasks.

Step 1: Start DFS at node D (no incoming edges)

Visited: D
Stack: []

Why: We start with a node that has no dependencies to ensure order.

Step 2: From D, visit A

Visited: D, A
Stack: []

Why: A depends on D, so we visit A after D.

Step 3: From A, visit B

Visited: D, A, B
Stack: []

Why: B depends on A, so we visit B after A.

Step 4: From B, visit C

Visited: D, A, B, C
Stack: []

Why: C depends on B, so we visit C after B.

Step 5: C has no neighbors, add C to stack

Stack: [C]

Why: No more dependencies from C, so we add it to the order.

Step 6: Back to B, add B to stack

Stack: [C, B]

Why: All dependencies of B visited, add B.

Step 7: Back to A, add A to stack

Stack: [C, B, A]

Why: All dependencies of A visited, add A.

Step 8: Back to D, add D to stack

Stack: [C, B, A, D]

Why: All dependencies of D visited, add D.

Result:

Stack (reversed) gives order: D -> A -> B -> C

Annotated Code

DSA Rust

use std::collections::{HashMap, HashSet};

struct Graph {
    adj_list: HashMap<char, Vec<char>>,
}

impl Graph {
    fn new() -> Self {
        Graph { adj_list: HashMap::new() }
    }

    fn add_edge(&mut self, from: char, to: char) {
        self.adj_list.entry(from).or_default().push(to);
        self.adj_list.entry(to).or_default(); // ensure 'to' node exists
    }

    fn topological_sort(&self) -> Vec<char> {
        let mut visited = HashSet::new();
        let mut stack = Vec::new();

        fn dfs(
            node: char,
            graph: &HashMap<char, Vec<char>>,
            visited: &mut HashSet<char>,
            stack: &mut Vec<char>,
        ) {
            visited.insert(node); // mark node visited
            if let Some(neighbors) = graph.get(&node) {
                for &neighbor in neighbors {
                    if !visited.contains(&neighbor) {
                        dfs(neighbor, graph, visited, stack); // visit dependents first
                    }
                }
            }
            stack.push(node); // add node after dependents
        }

        for &node in self.adj_list.keys() {
            if !visited.contains(&node) {
                dfs(node, &self.adj_list, &mut visited, &mut stack); // start DFS
            }
        }

        stack.reverse(); // reverse to get correct order
        stack
    }
}

fn main() {
    let mut graph = Graph::new();
    graph.add_edge('A', 'B');
    graph.add_edge('B', 'C');
    graph.add_edge('D', 'A');
    graph.add_edge('D', 'C');

    let order = graph.topological_sort();
    let output = order.iter().map(|c| c.to_string()).collect::<Vec<_>>().join(" -> ");
    println!("{}", output);
}

visited.insert(node);

mark current node as visited to avoid revisiting

for &neighbor in neighbors { if !visited.contains(&neighbor) { dfs(neighbor, graph, visited, stack); } }

visit all neighbors (dependents) recursively before current node

stack.push(node);

add node to stack after visiting all dependents

for &node in self.adj_list.keys() { if !visited.contains(&node) { dfs(node, &self.adj_list, &mut visited, &mut stack); } }

start DFS from all nodes not yet visited

stack.reverse();

reverse stack to get topological order

Output

D -> A -> B -> C

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for the recursion stack, visited set, and output stack

vs Alternative: Compared to Kahn's BFS approach, DFS uses recursion and stack but both have similar time complexity; DFS is often simpler to implement recursively.

Edge Cases

Empty graph

Returns empty order without errors

DSA Rust

for &node in self.adj_list.keys() { if !visited.contains(&node) { dfs(node, &self.adj_list, &mut visited, &mut stack); } }

Graph with single node and no edges

Returns list with single node

DSA Rust

stack.push(node);

Graph with disconnected components

Visits all components and returns combined topological order

DSA Rust

for &node in self.adj_list.keys() { if !visited.contains(&node) { dfs(node, &self.adj_list, &mut visited, &mut stack); } }

When to Use This Pattern

When you need to order tasks with dependencies and detect a sequence where each task comes after its prerequisites, use topological sort with DFS to explore dependencies deeply before adding tasks to the order.

Common Mistakes

Mistake: Adding the node to the order before visiting its dependents
Fix: Add the node to the stack only after all its neighbors (dependents) have been visited

Mistake: Not marking nodes as visited, causing infinite recursion
Fix: Use a visited set to track and skip already visited nodes

Mistake: Not reversing the stack at the end, resulting in reversed order
Fix: Reverse the stack before returning to get correct topological order

Summary

It finds an order to complete tasks so all dependencies come before dependent tasks using DFS.

Use it when you have tasks with dependencies and need a valid sequence to complete them.

The key insight is to visit all dependents first, then add the task, so the final reversed stack gives the correct order.

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