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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Topological Sort on a Simple DAG

What is the output of the following Rust code performing a topological sort using DFS on the given graph?

DSA Rust

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

fn dfs(node: usize, graph: &HashMap<usize, Vec<usize>>, visited: &mut HashSet<usize>, stack: &mut Vec<usize>) {
    if visited.contains(&node) {
        return;
    }
    visited.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            dfs(neighbor, graph, visited, stack);
        }
    }
    stack.push(node);
}

fn topological_sort(graph: &HashMap<usize, Vec<usize>>) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    for &node in graph.keys() {
        dfs(node, graph, &mut visited, &mut stack);
    }
    stack.reverse();
    stack
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(5, vec![2, 0]);
    graph.insert(4, vec![0, 1]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![1]);
    graph.insert(0, vec![]);
    graph.insert(1, vec![]);

    let order = topological_sort(&graph);
    println!("{:?}", order);
}

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

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

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

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

💡 Hint

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

The DFS visits nodes starting from 5 and 4. Node 5 leads to 2 and 0, and 2 leads to 3, which leads to 1. Node 4 leads to 0 and 1. The final reversed stack gives the order [5, 4, 2, 3, 1, 0].

❓ Predict Output

intermediate

Detecting Cycle Impact on Topological Sort

What error or output does the following Rust code produce when performing topological sort using DFS on a graph with a cycle?

DSA Rust

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

fn dfs(node: usize, graph: &HashMap<usize, Vec<usize>>, visited: &mut HashSet<usize>, stack: &mut Vec<usize>, rec_stack: &mut HashSet<usize>) -> bool {
    if rec_stack.contains(&node) {
        return true; // cycle detected
    }
    if visited.contains(&node) {
        return false;
    }
    visited.insert(node);
    rec_stack.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if dfs(neighbor, graph, visited, stack, rec_stack) {
                return true;
            }
        }
    }
    rec_stack.remove(&node);
    stack.push(node);
    false
}

fn topological_sort(graph: &HashMap<usize, Vec<usize>>) -> Result<Vec<usize>, &'static str> {
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    let mut rec_stack = HashSet::new();
    for &node in graph.keys() {
        if dfs(node, graph, &mut visited, &mut stack, &mut rec_stack) {
            return Err("Cycle detected, topological sort not possible");
        }
    }
    stack.reverse();
    Ok(stack)
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![1]);

    match topological_sort(&graph) {
        Ok(order) => println!("{:?}", order),
        Err(e) => println!("{}", e),
    }
}

A [1, 2, 3]

B Cycle detected, topological sort not possible

C Stack overflow error

D [3, 2, 1]

💡 Hint

Check how the recursion stack is used to detect cycles.

The code detects a cycle because node 1 leads to 2, 2 leads to 3, and 3 leads back to 1. The recursion stack detects this cycle and returns an error message.

🔧 Debug

advanced

Identify the Bug in DFS Topological Sort Implementation

The following Rust code attempts to perform a topological sort using DFS but produces incorrect output. What is the bug?

DSA Rust

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

fn dfs(node: usize, graph: &HashMap<usize, Vec<usize>>, visited: &mut HashSet<usize>, stack: &mut Vec<usize>) {
    if visited.contains(&node) {
        return;
    }
    visited.insert(node);
    stack.push(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            dfs(neighbor, graph, visited, stack);
        }
    }
}

fn topological_sort(graph: &HashMap<usize, Vec<usize>>) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    for &node in graph.keys() {
        dfs(node, graph, &mut visited, &mut stack);
    }
    stack
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(1, vec![2]);
    graph.insert(2, vec![3]);
    graph.insert(3, vec![]);

    let order = topological_sort(&graph);
    println!("{:?}", order);
}

A Stack is reversed twice causing wrong order

B Visited set is not updated correctly, causing infinite recursion

C Graph keys are not iterated properly, missing some nodes

D Nodes are pushed to stack before visiting neighbors, so order is incorrect

💡 Hint

Think about when nodes should be added to the stack in DFS for topological sort.

In topological sort using DFS, nodes must be added to the stack only after all their neighbors are visited. Here, nodes are pushed before visiting neighbors, causing incorrect order.

🧠 Conceptual

advanced

Understanding the Role of Recursion Stack in Cycle Detection

Why is a recursion stack (or call stack tracking) necessary in DFS-based topological sort implementations to detect cycles?

A Because it tracks nodes currently in the path to detect back edges indicating cycles

B Because it stores the final topological order of nodes

C Because it keeps track of visited nodes to avoid revisiting

D Because it helps in reversing the order of nodes after DFS

💡 Hint

Think about how cycles appear in DFS traversal.

The recursion stack tracks nodes currently being explored. If during DFS we revisit a node in this stack, it means a cycle exists (a back edge). This is essential to detect cycles in directed graphs.

🚀 Application

expert

Topological Sort Output for Complex Graph

Given the following directed graph edges, what is the topological sort order produced by DFS-based algorithm? Edges: (7->6), (7->5), (6->4), (5->4), (4->3), (3->2), (2->1), (1->0). Assume nodes with no outgoing edges are included.

DSA Rust

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

fn dfs(node: usize, graph: &HashMap<usize, Vec<usize>>, visited: &mut HashSet<usize>, stack: &mut Vec<usize>) {
    if visited.contains(&node) {
        return;
    }
    visited.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            dfs(neighbor, graph, visited, stack);
        }
    }
    stack.push(node);
}

fn topological_sort(graph: &HashMap<usize, Vec<usize>>) -> Vec<usize> {
    let mut visited = HashSet::new();
    let mut stack = Vec::new();
    for &node in graph.keys() {
        dfs(node, graph, &mut visited, &mut stack);
    }
    stack.reverse();
    stack
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(7, vec![6, 5]);
    graph.insert(6, vec![4]);
    graph.insert(5, vec![4]);
    graph.insert(4, vec![3]);
    graph.insert(3, vec![2]);
    graph.insert(2, vec![1]);
    graph.insert(1, vec![0]);
    graph.insert(0, vec![]);

    let order = topological_sort(&graph);
    println!("{:?}", order);
}

A [7, 5, 6, 4, 3, 2, 1, 0]

B [7, 6, 5, 4, 3, 2, 0, 1]

C [7, 6, 5, 4, 3, 2, 1, 0]

D [0, 1, 2, 3, 4, 5, 6, 7]

💡 Hint

Remember that DFS explores neighbors fully before pushing the node to stack.

Starting from node 7, DFS visits 6 then 4 then 3 then 2 then 1 then 0, pushing nodes after visiting neighbors. Node 5 is visited after 6, also leading to 4 but already visited. The reversed stack is [7, 6, 5, 4, 3, 2, 1, 0].

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