Kahn's Algorithm

KahnsAlgorithmForTopSort.py

# Leetcode 210:  Kahn's Algorithm
# https://www.youtube.com/watch?v=cIBFEhD77b4

from collections import defaultdict, deque
from typing import List, Tuple

def kahn_toposort(n: int, edges: List[Tuple[int, int]]) -> List[int]:
    # create adjacency graph as a dictionary where each node maps to its neighbors
    graph = defaultdict(list)
    # indegree list using list comprehension, initially all 0
    indeg = [0 for _ in range(n)]

    # build the graph and compute indegrees
    for u, v in edges:
        graph[u].append(v)   # add edge u -> v
        indeg[v] += 1        # increment indegree of v

    # initialize queue with all nodes having indegree 0
    dq = deque([i for i in range(n) if indeg[i] == 0])

    order = []                  # list to store topological order
    while dq:                   # loop until dq is not empty
        u = dq.popleft()        # take one node with indegree 0
        order.append(u)         # add it to the result order
        for v in graph[u]:      # for every neighbor of u
            indeg[v] -= 1       # reduce indegree (u is "removed")
            if indeg[v] == 0:   # if v has no more incoming edges
                dq.append(v)    # push v into the queue

    # if lenght of order is equal to no. of nodes, return order; otherwise, cycle detected return empty list
    return order if len(order) == n else []