Kahn algorithm

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.

Exercise 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())).

Show example 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()))

Test yourself

Kahn algorithm: match the terms

queue

Zero degree
order

Result
indegree

Degree
neighbor

Decrease
What is the topological order for the example DAG?
- [1, 0, 3, 2]
- [3, 2, 1, 0]
- [0, 1, 2, 3]
- [0, 3, 1, 2]
Show answer

[0, 1, 2, 3] — 0 is independent, others follow.
Queue operation
```
u = queue.pop(____)
```
Show answer
```
u = queue.pop(0)
```

Next lesson: Summary - Topological sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies