Graph Theory37 sections · 1633 units
Open in Course

Kahn's Algorithm - Implementation

The Template

Here is Kahn's algorithm:

function kahnTopoSort(n, adj):
    indegree = array of size n, all 0
    for u from 0 to n - 1:
        for v in adj[u]:
            indegree[v] = indegree[v] + 1

    q = queue
    for u from 0 to n - 1:
        if indegree[u] == 0:
            q.push(u)

    order = empty list
    while q is not empty:
        u = q.pop()
        order.append(u)
        for v in adj[u]:
            indegree[v] = indegree[v] - 1
            if indegree[v] == 0:
                q.push(v)

    if order.size != n:
        return "CYCLE DETECTED"
    return order

Time: O(V+E)O(V + E). Space: O(V)O(V).