Topological Sort Using Kahn's Algorithm BFS in DSA Rust - Build from Scratch

Topological Sort Using Kahn's Algorithm BFS

📖 Scenario: You are managing tasks in a project where some tasks must be done before others. You want to find an order to do all tasks without breaking any rules.

🎯 Goal: Build a Rust program that uses Kahn's Algorithm with BFS to find a valid order of tasks (topological sort) from given dependencies.

📋 What You'll Learn

Create a graph using adjacency list representation with exact tasks and edges

Create an in-degree vector to count incoming edges for each task

Implement Kahn's Algorithm using a queue to process tasks with zero in-degree

Print the final topological order of tasks separated by spaces

💡 Why This Matters

🌍 Real World

Topological sorting is used in project management, build systems, and scheduling where tasks have dependencies.

💼 Career

Understanding topological sort helps in roles like software engineering, data engineering, and systems design where dependency resolution is critical.

1

Create the graph adjacency list

Create a variable called graph as a vector of vectors of usize with 6 empty vectors to represent 6 tasks numbered 0 to 5. Then add edges exactly as follows: 5 -> 2, 5 -> 0, 4 -> 0, 4 -> 1, 2 -> 3, 3 -> 1.

DSA Rust

let mut graph: Vec> = vec![vec![]; 6];
// Your code here

Hint

Use vec![vec![]; 6] to create 6 empty vectors inside graph. Then use graph[index].push(value) to add edges.

2

Create the in-degree vector

Create a mutable vector called in_degree of usize with 6 zeros. Then use a for loop with variable edges to iterate over graph.iter() and inside it use another for loop with variable &node to iterate over edges. For each node, increment in_degree[node] by 1.

DSA Rust

fn main() {
    let mut graph: Vec> = vec![vec![]; 6];
    graph[5].push(2);
    graph[5].push(0);
    graph[4].push(0);
    graph[4].push(1);
    graph[2].push(3);
    graph[3].push(1);

    let mut in_degree = vec![0; 6];
    // Your code here
}

Hint

Use nested loops to count how many edges point to each node and store counts in in_degree.

3

Implement Kahn's Algorithm BFS

Create a mutable vector called queue of usize. Use a for loop with variable i from 0 to 5 to push i into queue if in_degree[i] is 0. Create an empty vector called topo_order of usize. Use a while loop that runs while queue is not empty. Inside, remove the first element from queue into variable node and push node into topo_order. Then iterate over graph[node] with variable &neighbor. For each neighbor, decrement in_degree[neighbor] by 1. If in_degree[neighbor] becomes 0, push neighbor into queue.

DSA Rust

fn main() {
    let mut graph: Vec> = vec![vec![]; 6];
    graph[5].push(2);
    graph[5].push(0);
    graph[4].push(0);
    graph[4].push(1);
    graph[2].push(3);
    graph[3].push(1);

    let mut in_degree = vec![0; 6];
    for edges in graph.iter() {
        for &node in edges.iter() {
            in_degree[node] += 1;
        }
    }

    let mut queue = Vec::new();
    // Your code here
}

Hint

Use a queue to process nodes with zero in-degree and update neighbors' in-degree accordingly.

4

Print the topological order

Use println! macro to print the elements of topo_order separated by spaces on one line.

DSA Rust

fn main() {
    // previous code

    println!("{}", topo_order.iter().map(|x| x.to_string()).collect::>().join(" "));
    // Your code here
}

Hint

Use println! with join(" ") to print the order separated by spaces.

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