Topological Sorting: When Order Matters

When you’re halfway through a macramé plant hanger, you can’t just jump to row eight. Row eight needs row seven, which needs row six, which needs the mounting ring. The cords have dependencies.

This is exactly what topological sorting solves: given a directed acyclic graph where edges mean “A must come before B,” produce a valid ordering. Kahn’s algorithm (1962) does this by repeatedly removing nodes with no incoming edges—tasks that have no prerequisites.

In Go, tracking in-degrees and a queue:

func topoSort(graph map[string][]string) []string {
    inDegree := make(map[string]int)
    for node := range graph {
        for _, neighbor := range graph[node] {
            inDegree[neighbor]++
        }
    }
    queue := []string{}
    for node := range graph {
        if inDegree[node] == 0 { queue = append(queue, node) }
    }
    result := []string{}
    for len(queue) > 0 {
        node := queue[0]; queue = queue[1:]
        result = append(result, node)
        for _, neighbor := range graph[node] {
            inDegree[neighbor]--
            if inDegree[neighbor] == 0 { queue = append(queue, neighbor) }
        }
    }
    return result
}

Lua takes a similar approach with tables:

function topo_sort(graph)
    local in_degree = {}
    for node, neighbors in pairs(graph) do
        in_degree[node] = in_degree[node] or 0
        for _, neighbor in ipairs(neighbors) do
            in_degree[neighbor] = (in_degree[neighbor] or 0) + 1
        end
    end
    local queue, result = {}, {}
    for node, degree in pairs(in_degree) do
        if degree == 0 then table.insert(queue, node) end
    end
    while #queue > 0 do
        local node = table.remove(queue, 1)
        table.insert(result, node)
        for _, neighbor in ipairs(graph[node] or {}) do
            in_degree[neighbor] = in_degree[neighbor] - 1
            if in_degree[neighbor] == 0 then table.insert(queue, neighbor) end
        end
    end
    return result
end

Build systems use this constantly: compile main.o only after util.o and config.o exist. Package managers use it too. Three dependencies each with two of their own? Topological sort finds an installation order that never breaks.

The algorithm runs in O(V+E)—linear in the graph size. Both implementations handle cycles by producing incomplete output (the queue empties before all nodes are processed). In macramé, a cycle would mean row five depends on row seven, which is impossible. In software, it means your build is broken.