What is Topological Sort?

Topological sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It's commonly used for scheduling tasks with dependencies.

How does Kahn's algorithm for Topological Sort work?

Kahn's algorithm works by first finding all nodes with an in-degree of 0 and adding them to a queue. It then repeatedly dequeues a node, adds it to the sorted list, and decrements the in-degree of its neighbors. If a neighbor's in-degree becomes 0, it's added to the queue. The process continues until the queue is empty.

Graph Algorithms

Topological Sort: Kahn's Algorithm

An essential algorithm for ordering tasks with dependencies, Kahn's algorithm provides an intuitive, queue-based approach to sorting Directed Acyclic Graphs (DAGs).

Kahn's Algorithm in Python

Here is a Python implementation of Kahn's algorithm for topological sorting.

from collections import deque

def topological_sort_kahn(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in in_degree if in_degree[u] == 0])
    top_order = []

    while queue:
        u = queue.popleft()
        top_order.append(u)

        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(top_order) == len(graph):
        return top_order
    else:
        return []  # Graph has a cycle

AI Coach Hint: Kahn's algorithm is not just for sorting; it's also a great way to detect cycles in a graph. If the number of nodes in the topological order is not equal to the total number of nodes in the graph, it means there's at least one cycle.