Kahn algorithm
- Algorithms course
- Advanced
- Lesson 47/56
- 4 min
Use in-degree counts to order vertices.
Kahn algorithm
Kahn's algorithm adds zero in-degree nodes to a queue. A node is dequeued, added to the order, and its neighbors' degrees are decreased.
Neighbors whose degree drops to zero are added to the queue. When the queue empties, the order is complete.
Order completion
When the queue is empty, if the order array contains all nodes, the process succeeded. If the order has fewer than n nodes, the graph has a cycle and no topological order exists.
Kahn's algorithm both orders and detects cycles this way. The output is the dependency order of the nodes.
Practice kahn_sort function
Write kahn_sort(graph). compute_indegree is given; queue zero-degree nodes, sort. Print [0, 1, 2, 3] with print(kahn_sort(init_graph())).
Starter code
def init_graph():
# Return adjacency list
return [[1, 2], [3], [3], []]
def compute_indegree(graph):
# Compute in-degrees
n = len(graph)
indegree = [0] * n
for u in range(n):
for v in graph[u]:
indegree[v] += 1
return indegree
def kahn_sort(graph):
# Find topological orderSample solution
def init_graph():
# Return adjacency list
return [[1, 2], [3], [3], []]
def compute_indegree(graph):
# Compute in-degrees
n = len(graph)
indegree = [0] * n
for u in range(n):
for v in graph[u]:
indegree[v] += 1
return indegree
def kahn_sort(graph):
# Find topological order
n = len(graph)
indegree = compute_indegree(graph)
queue = [i for i in range(n) if indegree[i] == 0]
order = []
while queue:
u = queue.pop(0)
order.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
queue.append(v)
return order
print(kahn_sort(init_graph()))Expected output
[0, 1, 2, 3]
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Kahn algorithm: match the terms
| Term | Meaning |
|---|---|
queue |
Zero degree |
order |
Result |
indegree |
Degree |
neighbor |
Decrease |
2 What is the topological order for the example DAG?
- [1, 0, 3, 2]
- [3, 2, 1, 0]
- [0, 1, 2, 3] Correct answer
- [0, 3, 1, 2]
Explanation: 0 is independent, others follow.
3 Queue operation
u = queue.pop(____)u = queue.pop(0)Explanation: 0 is right.