Topological Sort Using DFS in DSA Rust - Time & Space Complexity

Time Complexity: Topological Sort Using DFS

O(n + e)

Understanding Time Complexity

We want to understand how the time needed to perform topological sort using DFS changes as the graph size grows.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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);
}

fn topological_sort(graph: &Vec<Vec<usize>>, n: usize) -> Vec<usize> {
    let mut visited = vec![false; n];
    let mut stack = Vec::new();
    for node in 0..n {
        if !visited[node] {
            dfs(node, graph, &mut visited, &mut stack);
        }
    }
    stack.reverse();
    stack
}
    

This code performs a topological sort on a directed graph using depth-first search (DFS).

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: DFS visits each node and explores all its neighbors recursively.
• How many times: Each node is visited exactly once, and each edge is explored once during the DFS calls.

How Execution Grows With Input

The work grows with the number of nodes and edges. For example:

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 15 edges	About 25 operations (visiting nodes + edges)
100 nodes, 200 edges	About 300 operations
1000 nodes, 5000 edges	About 6000 operations

Pattern observation: The operations grow roughly proportional to nodes plus edges combined.

Final Time Complexity

Time Complexity: O(n + e)

This means the time grows linearly with the total number of nodes and edges in the graph.

Common Mistake

[X] Wrong: "DFS visits each node multiple times, so complexity is higher than linear."

[OK] Correct: Each node is marked visited and processed only once, so DFS does not repeat work on the same node.

Interview Connect

Understanding this time complexity helps you explain how graph algorithms scale and why DFS-based topological sort is efficient for dependency resolution.

Self-Check

"What if the graph is represented using an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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