Topological Sort Using DFS in DSA Rust - Build from Scratch

Topological Sort Using DFS

📖 Scenario: You are managing tasks in a project where some tasks must be done before others. This order is important to finish the project correctly.We will use a graph to represent tasks and their dependencies, then find a sequence to do all tasks without breaking any rules.

🎯 Goal: Build a program that uses Depth-First Search (DFS) to perform a topological sort on a directed graph of tasks.This will give a valid order to complete all tasks respecting their dependencies.

📋 What You'll Learn

Create a graph using a Rust HashMap with tasks as keys and vectors of dependent tasks as values

Add a visited HashMap to track which tasks have been checked

Implement a DFS function to explore tasks and their dependencies

Use DFS to build a topological order list

Print the final topological order of tasks

💡 Why This Matters

🌍 Real World

Topological sorting is used in project management, build systems, and scheduling where tasks depend on others.

💼 Career

Understanding topological sort and DFS is important for software engineers working on compilers, task schedulers, and dependency resolution.

1

Create the graph of tasks

Create a HashMap called graph with these exact entries: "A" points to vec!["C"], "B" points to vec!["C", "D"], "C" points to vec!["E"], "D" points to vec!["F"], and "E" and "F" point to empty vectors.

DSA Rust

# Create the graph HashMap with tasks and dependencies
# Your code here

Hint

Use HashMap::new() and insert to add each task and its dependencies.

2

Add visited map to track tasks

Create a mutable HashMap called visited with keys of type &str and values of type bool. Initialize it empty.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A", vec!["C"]);
    graph.insert("B", vec!["C", "D"]);
    graph.insert("C", vec!["E"]);
    graph.insert("D", vec!["F"]);
    graph.insert("E", vec![]);
    graph.insert("F", vec![]);

    // Create visited HashMap
    // Your code here
}

Hint

Use HashMap::new() to create an empty map for visited tasks.

3

Implement DFS function and run it

Define a function dfs that takes node: &str, graph: &HashMap<&str, Vec<&str>>, visited: &mut HashMap<&str, bool>, and stack: &mut Vec<&str>. In dfs, mark node as visited, recursively call dfs on unvisited neighbors, then push node to stack. In main, create an empty stack vector, loop over all keys in graph, and call dfs on unvisited nodes.

DSA Rust

use std::collections::HashMap;

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A", vec!["C"]);
    graph.insert("B", vec!["C", "D"]);
    graph.insert("C", vec!["E"]);
    graph.insert("D", vec!["F"]);
    graph.insert("E", vec![]);
    graph.insert("F", vec![]);

    let mut visited: HashMap = HashMap::new();

    // Define dfs function and run it on all nodes
    // Your code here
}

Hint

Use recursion to visit neighbors and push nodes to stack after visiting all dependencies.

4

Print the topological order

In main, after DFS calls, reverse the stack vector and print the tasks in order separated by spaces using println!.

DSA Rust

use std::collections::HashMap;

fn dfs(
    node: &str,
    graph: &HashMap>,
    visited: &mut HashMap,
    stack: &mut Vec,
) {
    visited.insert(node, true);
    if let Some(neighbors) = graph.get(node) {
        for &neighbor in neighbors {
            if !visited.get(neighbor).unwrap_or(&false) {
                dfs(neighbor, graph, visited, stack);
            }
        }
    }
    stack.push(node);
}

fn main() {
    let mut graph: HashMap> = HashMap::new();
    graph.insert("A", vec!["C"]);
    graph.insert("B", vec!["C", "D"]);
    graph.insert("C", vec!["E"]);
    graph.insert("D", vec!["F"]);
    graph.insert("E", vec![]);
    graph.insert("F", vec![]);

    let mut visited: HashMap = HashMap::new();
    let mut stack: Vec = Vec::new();

    for &node in graph.keys() {
        if !visited.get(node).unwrap_or(&false) {
            dfs(node, &graph, &mut visited, &mut stack);
        }
    }

    // Print the topological order
    // Your code here
}

Hint

Reverse the stack vector and join the elements with spaces before printing.

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