Topological Sort Using Kahn's Algorithm BFS in DSA Python - Time & Space Complexity

Time Complexity: Topological Sort Using Kahn's Algorithm BFS

O(n + e)

Understanding Time Complexity

We want to understand how the time needed to perform topological sort using Kahn's Algorithm grows as the graph size increases.

Specifically, how the number of nodes and edges affects the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

def kahn_topological_sort(graph, indegree):
    queue = deque()
    for node in indegree:
        if indegree[node] == 0:
            queue.append(node)
    topo_order = []
    while queue:
        current = queue.popleft()
        topo_order.append(current)
        for neighbor in graph[current]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
    return topo_order
    

This code performs topological sorting on a directed graph using Kahn's Algorithm with BFS.

Identify Repeating Operations

• Primary operation: Visiting each node once and checking all its outgoing edges.
• How many times: Each node is enqueued and dequeued once; each edge is checked once when reducing indegree.

How Execution Grows With Input

As the number of nodes (n) and edges (e) grow, the algorithm visits each node and edge once.

Input Size (n, e)	Approx. Operations
10 nodes, 15 edges	~25 operations (10 nodes + 15 edges)
100 nodes, 200 edges	~300 operations (100 + 200)
1000 nodes, 5000 edges	~6000 operations (1000 + 5000)

Pattern observation: The work grows roughly in proportion to the sum of nodes and edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time needed grows linearly with the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "The algorithm takes O(n²) time because it has nested loops."

[OK] Correct: The inner loop runs over edges of each node, so all edges are visited once total, not for every node. So it is linear in edges, not quadratic.

Interview Connect

Understanding this time complexity helps you explain how efficient topological sorting is on large graphs, a common topic in interviews.

Self-Check

"What if the graph was represented using an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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