Topological Sort Using Kahn's Algorithm BFS in DSA Rust - Execution Trace

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree for each node

↓

Add nodes with in-degree 0 to queue

↓

While queue not empty

Yes↓

Pop node from queue

↓

Add node to topological order

↓

For each neighbor of node

↓

Decrease neighbor's in-degree by 1

↓

If neighbor's in-degree is 0, add to queue

↩Back to While queue not empty

Start by counting incoming edges for each node. Nodes with zero incoming edges go into a queue. Remove nodes from the queue, add them to the order, and reduce in-degree of their neighbors. Repeat until all nodes are processed.

Execution Sample

DSA Rust

fn kahn_topological_sort(graph: &Vec<Vec<usize>>) -> Vec<usize> {
    let mut in_degree = vec![0; graph.len()];
    for edges in graph {
        for &v in edges {
            in_degree[v] += 1;
        }
    }
    let mut queue = Vec::new();
    for i in 0..graph.len() {
        if in_degree[i] == 0 {
            queue.push(i);
        }
    }
    let mut topo_order = Vec::new();
    while let Some(u) = queue.pop() {
        topo_order.push(u);
        for &v in &graph[u] {
            in_degree[v] -= 1;
            if in_degree[v] == 0 {
                queue.push(v);
            }
        }
    }
    topo_order
}

This Rust function performs topological sort using Kahn's algorithm on a graph represented as adjacency lists.

Execution Table

Step	Operation	Node Processed	In-degree Changes	Queue State	Topological Order	Graph State
1	Calculate in-degree	None	Node 1:1, Node 2:1, Node 3:2, Node 4:1	[]	[]	Graph: 0->[1,2], 1->[3], 2->[3,4], 3->[], 4->[]
2	Initialize queue	None	None	[0]	[]	Same as above
3	Pop from queue	0	None	[]	[0]	Same as above
4	Process neighbors of 0	0	Node 1:0, Node 2:0	[1,2]	[0]	Same as above
5	Pop from queue	2	None	[1]	[0,2]	Same as above
6	Process neighbors of 2	2	Node 3:1, Node 4:0	[1,4]	[0,2]	Same as above
7	Pop from queue	4	None	[1]	[0,2,4]	Same as above
8	Process neighbors of 4	4	None	[1]	[0,2,4]	Same as above
9	Pop from queue	1	None	[]	[0,2,4,1]	Same as above
10	Process neighbors of 1	1	Node 3:0	[3]	[0,2,4,1]	Same as above
11	Pop from queue	3	None	[]	[0,2,4,1,3]	Same as above
12	Process neighbors of 3	3	None	[]	[0,2,4,1,3]	Same as above
13	Queue empty	None	None	[]	[0,2,4,1,3]	End of algorithm

💡 Queue is empty, all nodes processed, topological order complete

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 6	After Step 10	Final
in_degree	[0,0,0,0,0]	[0,1,1,2,1]	[0,0,0,2,1]	[0,0,0,1,0]	[0,0,0,0,0]	[0,0,0,0,0]
queue	[]	[]	[1,2]	[1,4]	[3]	[]
topo_order	[]	[]	[0]	[0,2]	[0,2,4,1]	[0,2,4,1,3]

Key Moments - 3 Insights

Why do we add nodes with in-degree 0 to the queue at the start?

Nodes with in-degree 0 have no dependencies and can be placed first in the order. See execution_table row 2 where queue starts with node 0.

Why do we decrease in-degree of neighbors after processing a node?

Removing a node means its edges are removed, so neighbors lose one incoming edge. When in-degree hits 0, neighbors can be processed next. See execution_table rows 4 and 6.

What happens if the queue becomes empty before all nodes are processed?

It means there is a cycle and topological sort is impossible. Here, queue empties only after all nodes are processed (row 13).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the in-degree of node 3?

A 2

B 0

C 1

D 3

💡 Hint

Check the 'In-degree Changes' column at step 6 in execution_table

At which step does node 4 get added to the queue?

A Step 6

B Step 4

C Step 8

D Step 10

💡 Hint

Look at the 'Queue State' and 'In-degree Changes' columns in execution_table rows 4 to 7

If node 1 had an extra incoming edge, how would the initial queue change?

A Node 1 would still be in the initial queue

B Node 1 would not be in the initial queue

C Queue would be empty

D All nodes would be in the queue

💡 Hint

Refer to variable_tracker 'in_degree' and initial queue setup in execution_table step 2

Concept Snapshot

Topological Sort (Kahn's Algorithm):
- Calculate in-degree for all nodes
- Add nodes with in-degree 0 to queue
- While queue not empty:
  - Remove node, add to order
  - Decrease in-degree of neighbors
  - Add neighbors with in-degree 0 to queue
- Detect cycle if not all nodes processed

Full Transcript

Topological sort using Kahn's algorithm starts by counting how many edges come into each node. Nodes with zero incoming edges are added to a queue because they have no dependencies. Then, nodes are removed from the queue one by one, added to the topological order, and their neighbors' in-degree counts are decreased. If a neighbor's in-degree becomes zero, it is added to the queue. This process repeats until the queue is empty. If all nodes are processed, the topological order is complete. If the queue empties early, it means the graph has a cycle and no valid order exists. The execution table shows each step with the queue state, in-degree changes, and the growing topological order. The variable tracker follows key variables like in-degree, queue, and the order. Key moments clarify why nodes with zero in-degree start the queue, why in-degree decreases, and what cycle detection means. The visual quiz tests understanding of in-degree values, queue updates, and effects of extra edges. This method ensures a valid order of tasks respecting dependencies.

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