Topological Sort Using Kahn's Algorithm BFS in DSA Rust

Mental Model

We find an order to do tasks so that all dependencies come before the task itself. We start with tasks that have no dependencies and remove them step by step.

Analogy: Imagine you have to bake a cake but need to prepare ingredients first. You start with ingredients that don't depend on anything else, then use them to prepare the next steps, until the cake is ready.

Graph nodes with arrows showing dependencies:

A -> B -> C
↑
D

Start with nodes having no incoming arrows (no dependencies).

Dry Run Walkthrough

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

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

Step 1: Calculate in-degree (number of incoming edges) for each node: A=0, B=0, C=2, D=1

In-degree: A[0], B[0], C[2], D[1]

Why: We need to know which nodes have no dependencies to start with.

Step 2: Add nodes with in-degree 0 to queue: A, B

Queue: [A, B]

Why: These tasks can be done first as they have no dependencies.

Step 3: Remove A from queue and add to result; reduce in-degree of C by 1 (C=1)

Result: [A]
Queue: [B]
In-degree: C[1], D[1]

Why: Completing A reduces dependencies for C.

Step 4: Remove B from queue and add to result; reduce in-degree of C by 1 (C=0); add C to queue

Result: [A, B]
Queue: [C]
In-degree: C[0], D[1]

Why: Completing B frees C to be done next.

Step 5: Remove C from queue and add to result; reduce in-degree of D by 1 (D=0); add D to queue

Result: [A, B, C]
Queue: [D]
In-degree: D[0]

Why: Completing C frees D to be done last.

Step 6: Remove D from queue and add to result; no more nodes left

Result: [A, B, C, D]
Queue: []

Why: All tasks are completed in order respecting dependencies.

Result:

A -> B -> C -> D

Annotated Code

DSA Rust

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

fn kahn_topological_sort(edges: &[(char, char)]) -> Option<Vec<char>> {
    let mut in_degree = HashMap::new();
    let mut graph = HashMap::new();

    // Build graph and in-degree map
    for &(src, dst) in edges {
        graph.entry(src).or_insert_with(Vec::new).push(dst);
        *in_degree.entry(dst).or_insert(0) += 1;
        in_degree.entry(src).or_insert(0);
    }

    // Queue for nodes with in-degree 0
    let mut queue = VecDeque::new();
    for (&node, &deg) in &in_degree {
        if deg == 0 {
            queue.push_back(node);
        }
    }

    let mut result = Vec::new();

    while let Some(node) = queue.pop_front() {
        result.push(node); // Add node to result

        if let Some(neighbors) = graph.get(&node) {
            for &neighbor in neighbors {
                let deg = in_degree.get_mut(&neighbor).unwrap();
                *deg -= 1; // Reduce in-degree
                if *deg == 0 {
                    queue.push_back(neighbor); // Add to queue if no dependencies
                }
            }
        }
    }

    // Check if topological sort is possible (no cycle)
    if result.len() == in_degree.len() {
        Some(result)
    } else {
        None
    }
}

fn main() {
    let edges = [('A', 'C'), ('B', 'C'), ('C', 'D')];
    match kahn_topological_sort(&edges) {
        Some(order) => {
            for node in order {
                print!("{} ", node);
            }
            println!();
        }
        None => println!("Cycle detected, no topological order."),
    }
}

for &(src, dst) in edges { graph.entry(src).or_insert_with(Vec::new).push(dst); *in_degree.entry(dst).or_insert(0) += 1; in_degree.entry(src).or_insert(0); }

Build graph adjacency list and count incoming edges for each node

for (&node, &deg) in &in_degree { if deg == 0 { queue.push_back(node); } }

Initialize queue with nodes having zero dependencies

while let Some(node) = queue.pop_front() { result.push(node); if let Some(neighbors) = graph.get(&node) { for &neighbor in neighbors { let deg = in_degree.get_mut(&neighbor).unwrap(); *deg -= 1; if *deg == 0 { queue.push_back(neighbor); } } } }

Process nodes in queue, reduce in-degree of neighbors, add neighbors with zero in-degree to queue

if result.len() == in_degree.len() { Some(result) } else { None }

Check if all nodes processed to detect cycle

Output

A B C D 

Complexity Analysis

Time: O(V + E) because we visit each node and edge once during the process

Space: O(V + E) to store the graph and in-degree counts

vs Alternative: Compared to DFS-based topological sort, Kahn's algorithm uses BFS and explicit in-degree tracking, which can be easier to understand and detect cycles early.

Edge Cases

Empty graph (no nodes)

Returns empty order immediately

DSA Rust

if result.len() == in_degree.len() { Some(result) } else { None }

Graph with cycle (e.g., A->B, B->A)

Returns None indicating no valid topological order

DSA Rust

if result.len() == in_degree.len() { Some(result) } else { None }

Graph with single node and no edges

Returns list with that single node

DSA Rust

for (&node, &deg) in &in_degree { if deg == 0 { queue.push_back(node); } }

When to Use This Pattern

When you need to order tasks with dependencies and want to detect cycles, use Kahn's algorithm because it processes nodes with no dependencies first and removes them stepwise.

Common Mistakes

Mistake: Not initializing in-degree for nodes without incoming edges
Fix: Ensure to insert zero in-degree for all nodes when building the graph

Mistake: Not checking for cycles by comparing result length with total nodes
Fix: Add a final check to confirm all nodes were processed to detect cycles

Summary

Finds a valid order of tasks respecting dependencies using BFS and in-degree counts.

Use when you have a directed graph with dependencies and want to order nodes topologically.

Start with nodes having zero dependencies and remove them step by step to reveal the order.

Practice

1. What is the main purpose of Kahn's Algorithm in graph theory?

easy

A. To find a topological ordering of a Directed Acyclic Graph (DAG)

B. To find the shortest path between two nodes

C. To detect cycles in an undirected graph

D. To calculate the minimum spanning tree

Solution

1. Step 1: Understand Kahn's Algorithm goal

   Kahn's Algorithm is designed to produce a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge uv, vertex u comes before v in the ordering.

2. Step 2: Compare with other graph algorithms

   Shortest path algorithms find paths, cycle detection checks for loops, and minimum spanning tree algorithms work on undirected graphs. Kahn's Algorithm specifically produces a topological order.

3. Final Answer:

   To find a topological ordering of a Directed Acyclic Graph (DAG) -> Option A

4. Quick Check:

   Topological sort = Kahn's Algorithm purpose [OK]

Hint: Kahn's Algorithm always orders DAG nodes topologically [OK]

Common Mistakes:

• Confusing topological sort with shortest path
• Thinking it detects cycles in undirected graphs
• Mixing it with minimum spanning tree algorithms

2. Which Rust data structure is best suited to keep track of nodes with zero incoming edges in Kahn's Algorithm?

easy

A. HashMap

B. VecDeque (double-ended queue)

C. BinaryHeap

D. LinkedList

Solution

1. Step 1: Identify the need for queue behavior

   Kahn's Algorithm processes nodes with zero incoming edges in FIFO order, so a queue is needed to efficiently pop from front and push at back.

2. Step 2: Choose the Rust data structure

   VecDeque provides efficient push and pop operations at both ends, making it ideal for queue operations. HashMap is for key-value storage, BinaryHeap is a priority queue, and LinkedList is less efficient in Rust.

3. Final Answer:

   VecDeque (double-ended queue) -> Option B

4. Quick Check:

   Queue for zero in-degree nodes = VecDeque [OK]

Hint: Use VecDeque for queue operations in Rust [OK]

Common Mistakes:

• Using HashMap instead of a queue
• Choosing BinaryHeap which is a priority queue
• Using LinkedList which is inefficient in Rust

3. Given the following Rust code snippet implementing Kahn's Algorithm, what will be the printed topological order?

let edges = vec![(0, 1), (0, 2), (1, 3), (2, 3)];
let n = 4;
// Assume graph and in_degree are built correctly
// After running Kahn's Algorithm, the order vector is printed
println!("{:?}", order);

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 0, 2, 3]

Solution

1. Step 1: Analyze the graph edges and in-degree

   Edges: 0->1, 0->2, 1->3, 2->3. Node 0 has in-degree 0, nodes 1 and 2 have in-degree 1, node 3 has in-degree 2.

2. Step 2: Perform Kahn's Algorithm BFS

   Start with node 0 (in-degree 0). Remove it, reduce in-degree of 1 and 2 to 0. Add 1 and 2 to queue. Next, remove 1, then 2, then 3. Order is [0, 1, 2, 3]. However, since nodes 1 and 2 become zero in-degree simultaneously, the order of processing them can vary. If we process 2 before 1, the order is [0, 2, 1, 3], which is also valid.

3. Final Answer:

   [0, 2, 1, 3] -> Option C

4. Quick Check:

   Topological order respects edges = [0, 2, 1, 3] [OK]

Hint: Start with zero in-degree nodes and process neighbors [OK]

Common Mistakes:

• Reversing order of nodes processed
• Ignoring in-degree updates
• Assuming multiple valid orders without checking edges

4. Identify the bug in this Rust snippet of Kahn's Algorithm:

for &node in &graph[node] {
    in_degree[node] -= 1;
    if in_degree[node] == 0 {
        queue.push_back(node);
    }
}

medium

A. Missing initialization of in_degree array

B. Should use 'queue.push_front' instead of 'push_back'

C. Queue should be a stack for correct order

D. Using 'node' as loop variable shadows outer 'node', causing wrong indexing

Solution

1. Step 1: Understand variable shadowing in the loop

   The loop uses 'node' as the loop variable, which shadows the outer 'node' variable used to index graph. This causes confusion and incorrect indexing.

2. Step 2: Correct the variable naming

   Use a different variable name like 'neighbor' in the loop to avoid shadowing and correctly access neighbors.

3. Final Answer:

   Using 'node' as loop variable shadows outer 'node', causing wrong indexing -> Option D

4. Quick Check:

   Variable shadowing causes bugs = Using 'node' as loop variable shadows outer 'node', causing wrong indexing [OK]

Hint: Avoid reusing variable names in nested loops [OK]

Common Mistakes:

• Ignoring variable shadowing
• Confusing queue with stack usage
• Assuming in_degree initialization is the bug

5. You have a graph with edges: [(5, 2), (5, 0), (4, 0), (4, 1), (2, 3), (3, 1)]. Using Kahn's Algorithm, which of the following is a valid topological order?

hard

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

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

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

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

Solution

1. Step 1: Calculate in-degree for each node

   Nodes: 0,1,2,3,4,5 In-degree: 0(2), 1(2), 2(1), 3(1), 4(0), 5(0)

2. Step 2: Perform Kahn's Algorithm steps

   Start with nodes 4 and 5 (in-degree 0). Remove 5: reduce in-degree of 2 and 0. Remove 4: reduce in-degree of 0 and 1. Then remove 2, 3, 1, 0 in order. One valid order is [5, 4, 2, 3, 1, 0].

3. Final Answer:

   [5, 4, 2, 3, 1, 0] -> Option A

4. Quick Check:

   Valid topological order respects edges = [5, 4, 2, 3, 1, 0] [OK]

Hint: Start with zero in-degree nodes and remove edges stepwise [OK]

Common Mistakes:

• Choosing orders that violate edge directions
• Ignoring initial zero in-degree nodes
• Mixing node order without updating in-degree