Topological sort (Kahn's)

Order the nodes of a directed graph so every arrow points forward. Think build steps or course prerequisites.

Time O(V + E)Space O(V)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

A node with no incoming arrows depends on nothing, so it can go first. Output it, delete its outgoing arrows, and any node that now has no incoming arrows becomes ready.

Code

C++PythonC#

vector<char> topoSort(
        unordered_map<char, vector<char>>& graph, unordered_map<char, int>& indegree) {
    queue<char> q;
    for (auto& [v, d] : indegree) if (d == 0) q.push(v);
    vector<char> order;
    while (!q.empty()) {
        char u = q.front(); q.pop();
        order.push_back(u);
        for (char v : graph[u])
            if (--indegree[v] == 0) q.push(v);
    }
    return order; // fewer nodes than the graph means a cycle
}

from collections import deque

def topo_sort(graph: dict[str, list[str]], indegree: dict[str, int]) -> list[str]:
    queue = deque(v for v, d in indegree.items() if d == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0: queue.append(v)
    return order  # fewer nodes than the graph means a cycle

public static List<char> TopoSort(
        Dictionary<char, List<char>> graph, Dictionary<char, int> indegree) {
    var queue = new Queue<char>(
        indegree.Where(p => p.Value == 0).Select(p => p.Key));
    var order = new List<char>();
    while (queue.Count > 0) {
        char u = queue.Dequeue();
        order.Add(u);
        foreach (char v in graph[u])
            if (--indegree[v] == 0) queue.Enqueue(v);
    }
    return order; // fewer nodes than the graph means a cycle
}

Tips

If the result has fewer nodes than the graph, the leftover nodes are stuck in a cycle. This is the standard cycle check for directed graphs.
in=K under each node is its count of unfinished prerequisites.

In the .NET library

MSBuild project references and NuGet restore order are topological sorts of a dependency graph.