Kahn’s Topological Sort

Kahn's algorithm is a popular method for topological sorting of a directed acyclic graph (DAG). Topological sorting arranges the vertices of a DAG into a linear order such that for every directed edge u→vu \rightarrow vu→v, vertex uuu comes before vvv in the ordering.

ALGORITHM

Initialize: Compute the in-degree of each vertex (number of incoming edges).

Find Start Vertices: Identify vertices with in-degree zero and add them to a queue.

Topological Sort: While the queue is not empty, remove a vertex uuu from the queue, add it to the result list, and decrement the in-degree of its neighbors. If a neighbor's in-degree becomes zero, add it to the queue.

Repeat: Repeat step 3 until all vertices are processed.

Key Points

• Kahn's algorithm utilizes the concept of in-degree, which represents the number of incoming edges for each vertex.
• It iteratively removes vertices with in-degree zero (vertices without incoming edges) from the graph, ensuring that the removed vertices come before their neighbors in the topological ordering.
• The algorithm terminates when all vertices are processed or when a cycle is detected in the graph.

USE CASES

• Build Systems with Dependencies: Topological sorting is commonly used in build systems (e.g., Makefiles) to determine the order of compilation or execution of tasks with dependencies.
• Course Scheduling: Topological sorting can be used in academic institutions to schedule courses so that prerequisite courses are taken before their dependents.
• Task Scheduling: Topological sorting is used in task scheduling applications to order tasks based on dependencies or requirements.
• Package Dependency Resolution: In software package managers, topological sorting helps resolve dependencies between software packages during installation or upgrade processes.

Python

from collections import defaultdict

def topological_sort(graph):
    # Initialize a dictionary to store indegrees of all vertices
    indegree = defaultdict(int)
    # Initialize a list to store the sorted elements
    result = []

    # Calculate the indegrees of all vertices
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1

    # Initialize a queue for Kahn's algorithm
    queue = []

    # Add all vertices with indegree 0 to the queue
    for u in graph:
        if indegree[u] == 0:
            queue.append(u)

    # Kahn's algorithm
    while queue:
        u = queue.pop(0)
        result.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    # Check for cycles
    if len(result) != len(graph):
        raise ValueError("The graph has a cycle!")

    return result