Topological Sort Using Kahn's Algorithm BFS in DSA Python - 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 so that no task is done before its dependencies.

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

📋 What You'll Learn

Create a graph as a dictionary with tasks as keys and list of dependent tasks as values

Create an indegree dictionary to count how many prerequisites each task has

Use a queue to process tasks with zero indegree

Implement Kahn's Algorithm to produce a topological order

Print the final topological order as a list

💡 Why This Matters

🌍 Real World

Topological sorting is used in project management, build systems, and scheduling where some tasks depend on others.

💼 Career

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

1

Create the graph of task dependencies

Create a dictionary called graph with these exact entries: 1: [2, 3], 2: [4], 3: [4], 4: []

DSA Python

# Your code here

Hint

Think of graph as a map where each task points to tasks that depend on it.

2

Create the indegree dictionary for each task

Create a dictionary called indegree with keys 1, 2, 3, 4 and values representing how many tasks must be done before each task. Initialize all values to 0 first.

DSA Python

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
# Your code here

Hint

Start by setting all indegrees to zero before counting dependencies.

3

Calculate the indegree for each task

Use a for loop with variables node and neighbors to iterate over graph.items(). Inside it, use another for loop with variable neighbor to iterate over neighbors and increment indegree[neighbor] by 1.

DSA Python

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
indegree = {1: 0, 2: 0, 3: 0, 4: 0}
# Your code here

Hint

Count how many tasks point to each task to find indegree.

4

Perform Kahn's Algorithm and print the topological order

Import deque from collections. Create a queue with tasks having indegree zero. Create an empty list topo_order. Use a while loop to process tasks from queue. For each task, append it to topo_order and reduce indegree of its neighbors by 1. If any neighbor's indegree becomes zero, add it to queue. Finally, print topo_order.

DSA Python

graph = {1: [2, 3], 2: [4], 3: [4], 4: []}
indegree = {1: 0, 2: 0, 3: 0, 4: 0}
for node, neighbors in graph.items():
    for neighbor in neighbors:
        indegree[neighbor] += 1
# Your code here

Hint

Use a queue to process tasks with no prerequisites and build the order step by 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