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

Concept Flow - Topological Sort Using Kahn's Algorithm BFS

Calculate in-degree of all nodes

↓

Add nodes with in-degree 0 to queue

↓

While queue not empty

↓

Pop node from queue

↓

Add node to topological order

↓

For each neighbor

↓

Decrease in-degree of neighbor

↓

If in-degree becomes 0, add neighbor to queue

↓

Repeat until queue empty

↓

Check if topological order includes all nodes

↓

Return topological order or error if cycle

This flow shows how Kahn's algorithm uses in-degree counts and a queue to build a topological order by repeatedly removing nodes with zero in-degree.

Execution Sample

DSA Python

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}

# Kahn's Algorithm
in_degree = {0:0,1:1,2:1,3:2}
queue = [0]
topo_order = []
while queue:
    node = queue.pop(0)
    topo_order.append(node)
    for nbr in graph[node]:
        in_degree[nbr] -= 1
        if in_degree[nbr] == 0:
            queue.append(nbr)

This code performs topological sort on a directed graph using Kahn's BFS algorithm.

Execution Table

Step	Operation	Node Processed	Queue Before	In-degree Before	In-degree After	Queue After	Topological Order	Visual State
1	Initialize in-degree and queue	None	[]	{0:0,1:1,2:1,3:2}	{0:0,1:1,2:1,3:2}	[0]	[]	Graph: 0->1,2; 1->3; 2->3; 3->
2	Pop node from queue	0	[0]	{0:0,1:1,2:1,3:2}	{0:0,1:1,2:1,3:2}	[]	[0]	Processed 0; Queue: []; topo_order: [0]
3	Decrease in-degree of neighbors	0	[]	{0:0,1:1,2:1,3:2}	{0:0,1:0,2:0,3:2}	[1,2]	[0]	Neighbors 1,2 in-degree decreased; Queue: [1,2]
4	Pop node from queue	1	[1,2]	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:2}	[2]	[0,1]	Processed 1; Queue: [2]; topo_order: [0,1]
5	Decrease in-degree of neighbors	1	[2]	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:1}	[2]	[0,1]	Neighbor 3 in-degree decreased to 1; Queue unchanged
6	Pop node from queue	2	[2]	{0:0,1:0,2:0,3:1}	{0:0,1:0,2:0,3:1}	[]	[0,1,2]	Processed 2; Queue: []; topo_order: [0,1,2]
7	Decrease in-degree of neighbors	2	[]	{0:0,1:0,2:0,3:1}	{0:0,1:0,2:0,3:0}	[3]	[0,1,2]	Neighbor 3 in-degree decreased to 0; Queue: [3]
8	Pop node from queue	3	[3]	{0:0,1:0,2:0,3:0}	{0:0,1:0,2:0,3:0}	[]	[0,1,2,3]	Processed 3; Queue: []; topo_order: [0,1,2,3]
9	No neighbors to process	3	[]	{0:0,1:0,2:0,3:0}	{0:0,1:0,2:0,3:0}	[]	[0,1,2,3]	All nodes processed; topological order complete

💡 Queue is empty and all nodes processed; topological order found

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 7	Final
in_degree	{0:0,1:1,2:1,3:2}	{0:0,1:1,2:1,3:2}	{0:0,1:0,2:0,3:2}	{0:0,1:0,2:0,3:1}	{0:0,1:0,2:0,3:0}	{0:0,1:0,2:0,3:0}
queue	[]	[0]	[1,2]	[2]	[3]	[]
topo_order	[]	[]	[0]	[0,1]	[0,1,2]	[0,1,2,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 processed first. This is shown in execution_table row 1 where queue starts with node 0.

What happens if a node's in-degree never becomes 0?

It means there is a cycle and no valid topological order. The algorithm would end with some nodes unprocessed. Here, all nodes reach in-degree 0, so no cycle.

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

Because processing a node removes its outgoing edges, reducing dependencies of neighbors. See execution_table rows 3, 5, and 7 where in-degree decreases.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the queue after processing node 0?

A [0]

B [1, 2]

C []

D [3]

💡 Hint

Check the 'Queue After' column in row with Step 3 in execution_table.

At which step does node 3 first get added to the queue?

A Step 7

B Step 5

C Step 4

D Step 9

💡 Hint

Look at 'Queue After' and 'In-degree After' columns in execution_table rows 5 and 7.

If node 2 had an extra edge to node 1, how would the in-degree of node 1 change initially?

A It would stay the same

B It would decrease by 1

C It would increase by 1

D It would become zero

💡 Hint

In-degree counts incoming edges; adding an edge to node 1 increases its in-degree.

Concept Snapshot

Topological Sort using Kahn's Algorithm (BFS):
- Compute in-degree for all nodes
- Enqueue nodes with in-degree 0
- While queue not empty:
  - Dequeue node, add to order
  - Decrease in-degree of neighbors
  - Enqueue neighbors with in-degree 0
- If all nodes processed, order is valid
- Detects cycles if nodes remain unprocessed

Full Transcript

Kahn's algorithm for topological sort works by first calculating the in-degree (number of incoming edges) for each node in the graph. Nodes with zero in-degree are added to a queue because they have no dependencies and can be processed immediately. Then, the algorithm repeatedly removes nodes from the queue, adds them to the topological order, and decreases the in-degree of their neighbors. If any neighbor's in-degree becomes zero, it is added to the queue. This process continues until the queue is empty. If all nodes are processed, the topological order is complete. If some nodes remain unprocessed, it indicates a cycle in the graph and no valid topological order exists. The execution table traces these steps with the graph {0: [1, 2], 1: [3], 2: [3], 3: []}, showing how the queue, in-degree, and topological order change at each step.

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 detect cycles in an undirected graph

C. To find the shortest path between two nodes

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 u -> v, u comes before v in the ordering.

2. Step 2: Compare with other graph algorithms

   Other options describe different algorithms: cycle detection, shortest path, and minimum spanning tree are unrelated to Kahn's Algorithm.

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 finds order in DAGs [OK]

Common Mistakes:

• Confusing topological sort with cycle detection
• Thinking it works on undirected graphs
• Mixing it up with shortest path algorithms

2. Which of the following Python code snippets correctly initializes the in-degree array for Kahn's Algorithm given a graph adjacency list graph with n nodes?

easy

A. in_degree = [0] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1

B. in_degree = [0] * n
for v in range(n):
for u in graph[v]:
in_degree[v] += 1

C. in_degree = [1] * n
for u in range(n):
for v in graph[u]:
in_degree[v] += 1

D. in_degree = [0] * n
for u in graph:
for v in graph[u]:
in_degree[u] += 1

Solution

1. Step 1: Understand in-degree calculation

   In-degree of a node is the count of edges coming into it. For each edge u -> v, increment in_degree[v].

2. Step 2: Analyze code snippets

   in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 correctly loops over each node u and its neighbors v, incrementing in_degree[v]. in_degree = [0] * n for v in range(n): for u in graph[v]: in_degree[v] += 1 increments the source node incorrectly. in_degree = [1] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 initializes in_degree with 1s, which is wrong. in_degree = [0] * n for u in graph: for v in graph[u]: in_degree[u] += 1 increments in_degree[u], which is incorrect.

3. Final Answer:

   in_degree = [0] * n for u in range(n): for v in graph[u]: in_degree[v] += 1 -> Option A

4. Quick Check:

   Increment in_degree of destination node [OK]

Hint: Increment in-degree of target nodes, not source [OK]

Common Mistakes:

• Incrementing in-degree of source node instead of target
• Initializing in-degree with wrong default values
• Swapping loop variables u and v

3. What is the output of the following Python code implementing Kahn's Algorithm on the graph with edges: 0->1, 0->2, 1->3, 2->3?

from collections import deque

graph = {0: [1, 2], 1: [3], 2: [3], 3: []}
n = 4
in_degree = [0]*n
for u in range(n):
    for v in graph[u]:
        in_degree[v] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
topo_order = []
while queue:
    node = queue.popleft()
    topo_order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
print(topo_order)

medium

A. [0, 1, 2, 3]

B. [3, 1, 2, 0]

C. [0, 2, 1, 3]

D. [1, 2, 0, 3]

Solution

1. Step 1: Calculate in-degree and initialize queue

   In-degree: 0=0, 1=1, 2=1, 3=2. Queue starts with nodes having in-degree 0: [0].

2. Step 2: Process nodes in queue

   Pop 0, append to topo_order: [0]. Decrement in-degree of 1 and 2 to 0, add both to queue: [1, 2]. Pop 1, append: [0,1]. Decrement in-degree of 3 to 1. Pop 2, append: [0,1,2]. Decrement in-degree of 3 to 0, add 3 to queue: [3]. Pop 3, append: [0,1,2,3].

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Ignoring order of nodes with zero in-degree
• Not updating in-degree after popping nodes
• Appending nodes before in-degree reaches zero

4. Identify the error in the following Kahn's Algorithm code snippet and choose the correct fix:

from collections import deque

graph = {0: [1], 1: [2], 2: [0]}
n = 3
in_degree = [0]*n
for u in range(n):
    for v in graph[u]:
        in_degree[u] += 1
queue = deque([i for i in range(n) if in_degree[i] == 0])
topo_order = []
while queue:
    node = queue.popleft()
    topo_order.append(node)
    for neighbor in graph[node]:
        in_degree[neighbor] -= 1
        if in_degree[neighbor] == 0:
            queue.append(neighbor)
print(topo_order)

medium

A. Initialize in_degree with ones instead of zeros

B. Change 'in_degree[u] += 1' to 'in_degree[v] += 1' to correctly count incoming edges

C. Replace deque with list for queue implementation

D. Remove the while loop to avoid infinite processing

Solution

1. Step 1: Identify incorrect in-degree update

   The code increments in_degree[u] for edges u->v, but it should increment in_degree[v] because in-degree counts incoming edges to v.

2. Step 2: Understand impact on queue initialization

   Incorrect in-degree causes wrong zero in-degree nodes, so queue may be empty or incorrect, breaking the algorithm.

3. Final Answer:

   Change 'in_degree[u] += 1' to 'in_degree[v] += 1' to correctly count incoming edges -> Option B

4. Quick Check:

   Increment in-degree of target node, not source [OK]

Hint: In-degree counts edges coming into a node, increment target node [OK]

Common Mistakes:

• Incrementing in-degree of source node
• Not detecting cycles due to wrong in-degree
• Using wrong data structure for queue

5. Given a Directed Acyclic Graph (DAG) with nodes 0 to 5 and edges: 5->2, 5->0, 4->0, 4->1, 2->3, 3->1, which of the following is a valid topological order produced by Kahn's Algorithm?

hard

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

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

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

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

Solution

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

   In-degree: 0=2 (from 5,4), 1=2 (from 4,3), 2=1 (from 5), 3=1 (from 2), 4=0, 5=0. Start queue with nodes 4 and 5.

2. Step 2: Process nodes in queue and build order

   Pop 4: order=[4], decrement in-degree of 0 to 1 and 1 to 1. Pop 5: order=[4,5], assuming graph[5]=[0,2], decrement 0 to 0 and append 0, decrement 2 to 0 and append 2: queue=[0,2]. Pop 0: order=[4,5,0]. Pop 2: order=[4,5,0,2], decrement 3 to 0, append 3. Pop 3: order=[4,5,0,2,3], decrement 1 to 0, append 1. Pop 1: order=[4,5,0,2,3,1].

3. Final Answer:

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

4. Quick Check:

   Valid topological order respects edges [OK]

Hint: Start with zero in-degree nodes, remove edges, add new zero in-degree nodes [OK]

Common Mistakes:

• Ignoring in-degree counts leading to invalid order
• Placing nodes before their dependencies
• Assuming any order is valid without checking edges