DSA Topological Sort

How it works

Kahn’s method starts with zero-indegree vertices and removes their outgoing requirements as they are processed. Multiple zero-indegree choices can produce several valid orders; the example uses deterministic dictionary and neighbor order rather than claiming one universal answer. If some vertices remain after the ready queue empties, a directed cycle prevents a complete order. The returned sequence includes isolated vertices as well as connected dependencies.

Run the code

Select Try in playground to load this complete source into the existing Python editor. It does not run automatically; choose Run when ready. These examples use only the Python standard library and small fictional inputs. They do not need database services, extra packages or personal files.

For local work, save the complete source as topological-order.py and run python topological-order.py. The local review uses Python 3.12.14; the browser uses the existing Pyodide 0.27.7 runtime. Keep inputs small, respect explicit table/tour budgets and account for recursion limits before increasing a fixture’s size.

Example

def validate_graph(graph, weighted=False, nonnegative=False):
    if not isinstance(graph, dict):
        raise ValueError("Expected an adjacency dictionary")
    if any(not isinstance(vertex, str) for vertex in graph):
        raise ValueError("String vertex labels required")
    for vertex, neighbors in graph.items():
        for edge in neighbors:
            if weighted:
                target, weight = edge
                if type(weight) is not int or (nonnegative and weight < 0):
                    raise ValueError("Invalid integer edge weight")
            else:
                target = edge
            if target not in graph:
                raise ValueError("Unknown target vertex")

from collections import deque

def topological_order(graph):
    validate_graph(graph)
    incoming = {vertex: 0 for vertex in graph}
    for neighbors in graph.values():
        for target in neighbors:
            incoming[target] += 1
    pending = deque(vertex for vertex in graph if incoming[vertex] == 0)
    result = []
    while pending:
        vertex = pending.popleft()
        result.append(vertex)
        for target in graph[vertex]:
            incoming[target] -= 1
            if incoming[target] == 0:
                pending.append(target)
    if len(result) != len(graph):
        raise ValueError("Directed cycle prevents an ordering")
    return result

graph = {"collect": ["clean"], "clean": ["report"], "report": [], "label": []}
print(topological_order(graph))
try:
    topological_order({"a": ["b"], "b": ["a"]})
except ValueError as error:
    print(error)

Expected result

['collect', 'label', 'clean', 'report']
Directed cycle prevents an ordering

Collect precedes clean, which precedes report; the independent label task can occupy another valid position. The cycle fixture rejects instead of returning a partial sequence and describing it as complete. Tests verify edge ordering rather than only one hardcoded valid order.

Time, space and assumptions

Indegree construction and queue processing are O(V+E), with O(V) counters, queue and output. A priority-based choice among ready vertices would add a different ordering cost.