Topological Sort Using Kahn's Algorithm BFS in DSA Python

Mental Model

We order tasks so that each task comes after all tasks it depends on, by repeatedly picking tasks with no unmet dependencies.

Analogy: Imagine you have a list of chores where some chores must be done before others. You start with chores that have no prerequisites, do them, then remove them from the list, revealing new chores that can now be done.

Graph nodes with arrows showing dependencies:
A -> B -> C
↑
D

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

Queue starts with nodes having in-degree 0: [A, D]

Dry Run Walkthrough

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

Goal: Find an order of nodes so that every node appears after all nodes that point to it

Step 1: Calculate in-degree for each node: A=0, B=2, C=1, D=0

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

Why: We need to start with nodes that have no dependencies

Step 2: Remove A from queue and add to result

Result: [A]
Queue: [D]
Decrease in-degree of B by 1 (B=1)

Why: A is done, so B has one less dependency

Step 3: Remove D from queue and add to result

Result: [A, D]
Queue: []
Decrease in-degree of B by 1 (B=0)
Add B to queue

Why: D is done, B now has no dependencies and can be processed

Step 4: Remove B from queue and add to result

Result: [A, D, B]
Queue: []
Decrease in-degree of C by 1 (C=0)
Add C to queue

Why: B is done, so C can now be processed

Step 5: Remove C from queue and add to result

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

Why: C has no dependencies left, finish processing

Result:

Final order: A -> D -> B -> C

Annotated Code

DSA Python

from collections import deque, defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices

    def add_edge(self, u, v):
        self.graph[u].append(v)

    def kahn_topological_sort(self):
        in_degree = {u: 0 for u in self.graph}
        # Calculate in-degree of each node
        for u in self.graph:
            for v in self.graph[u]:
                in_degree[v] = in_degree.get(v, 0) + 1

        # Queue for nodes with in-degree 0
        queue = deque([u for u in in_degree if in_degree[u] == 0])
        result = []

        while queue:
            u = queue.popleft()  # Remove node with no dependencies
            result.append(u)

            # Decrease in-degree of neighbors
            for v in self.graph[u]:
                in_degree[v] -= 1
                if in_degree[v] == 0:
                    queue.append(v)  # Add new nodes with no dependencies

        if len(result) != len(in_degree):
            return "Cycle detected, topological sort not possible"
        return ' -> '.join(result)

# Driver code
if __name__ == '__main__':
    g = Graph(4)
    g.add_edge('A', 'B')
    g.add_edge('B', 'C')
    g.add_edge('D', 'B')

    print(g.kahn_topological_sort())

for u in self.graph: for v in self.graph[u]: in_degree[v] = in_degree.get(v, 0) + 1

Calculate in-degree for each node by counting incoming edges

queue = deque([u for u in in_degree if in_degree[u] == 0])

Initialize queue with nodes having zero in-degree (no dependencies)

while queue: u = queue.popleft() result.append(u)

Process nodes with no dependencies and add to result

for v in self.graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v)

Decrease in-degree of neighbors; enqueue if they have no remaining dependencies

if len(result) != len(in_degree): return "Cycle detected, topological sort not possible"

Check for cycles by comparing processed nodes count with total nodes

Output

A -> D -> B -> C

Complexity Analysis

Time: O(V + E) because we visit every node and edge once during in-degree calculation and BFS traversal

Space: O(V + E) for storing 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

Graph with cycle

Algorithm detects cycle and returns a message indicating topological sort is not possible

DSA Python

if len(result) != len(in_degree):
    return "Cycle detected, topological sort not possible"

Graph with isolated node (no edges)

Isolated node has in-degree 0 and is included in the result

DSA Python

queue = deque([u for u in in_degree if in_degree[u] == 0])

Empty graph

Returns empty result as there are no nodes

DSA Python

queue = deque([u for u in in_degree if in_degree[u] == 0])

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 unmet dependencies in BFS order.

Common Mistakes

Mistake: Not initializing in-degree for all nodes, missing nodes with zero in-degree
Fix: Initialize in-degree for all nodes before counting incoming edges

Mistake: Not checking for cycles by comparing processed nodes count with total nodes
Fix: Add a check after processing to detect if cycle exists

Mistake: Adding nodes to queue before their in-degree reaches zero
Fix: Only enqueue nodes when their in-degree becomes zero after decrement

Summary

It finds an order of nodes so that each node appears after all nodes it depends on.

Use it when you have tasks with dependencies and want to find a valid execution order or detect cycles.

The key insight is to repeatedly pick nodes with no remaining dependencies and remove them, revealing new nodes to process.

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