23. Topological Sort

🧸 ELI5: You can't put on your shoes before your socks. Some tasks must happen before others. Topological sort takes a pile of "this-before-that" rules and gives you one valid order to do everything in, respecting every rule.

🌍 Real life: Getting dressed in the right order (underwear → pants → belt). University course prerequisites (must take Calculus 1 before Calculus 2). Build systems compiling code (compile library A before the app that depends on it). Spreadsheet formulas that depend on other cells.

📝 Pseudocode (Kahn's algorithm, using in-degrees + a queue):

function topologicalSort(graph):
    inDegree = count incoming edges for every node
    queue = all nodes with inDegree == 0     // no prerequisites
    order = []

    while queue is not empty:
        node = dequeue(queue)
        order.add(node)
        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                enqueue(queue, neighbor)
    return order

🐹 Go:

package main

import "fmt"

func topologicalSort(graph map[string][]string) []string {
	inDegree := make(map[string]int)
	for node := range graph {
		inDegree[node] = 0
	}
	for _, deps := range graph {
		for _, dep := range deps {
			inDegree[dep]++
		}
	}

	var queue []string
	for node, degree := range inDegree {
		if degree == 0 {
			queue = append(queue, node) // no prerequisites — start here
		}
	}

	var order []string
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		order = append(order, current)

		for _, next := range graph[current] {
			inDegree[next]--
			if inDegree[next] == 0 {
				queue = append(queue, next)
			}
		}
	}
	return order
}

func main() {
	gettingDressed := map[string][]string{
		"Underwear": {"Pants"},
		"Pants":     {"Belt"},
		"Socks":     {"Shoes"},
		"Belt":      {},
		"Shoes":     {},
	}
	fmt.Println(topologicalSort(gettingDressed))
	// e.g. [Underwear Socks Pants Shoes Belt] — a valid order respecting all rules
}

🇨 C (Kahn's algorithm, same integer-indexed Graph shape as #14/#15, with the ready-to-schedule queue as a plain array):

#include <stdio.h>
#include <string.h>

#define MAX_NODES 8

typedef struct {
    char names[MAX_NODES][32];
    int  adj_list[MAX_NODES][MAX_NODES];
    int  adj_count[MAX_NODES];
    int  num_nodes;
} Graph;

int graph_add_node(Graph *g, const char *name) {
    strncpy(g->names[g->num_nodes], name, 31);
    return g->num_nodes++;
}

void graph_add_prereq(Graph *g, int before, int after) {
    g->adj_list[before][g->adj_count[before]++] = after; // "before" must happen before "after"
}

int topological_sort(Graph *g, int *order) {
    int in_degree[MAX_NODES] = {0};
    for (int i = 0; i < g->num_nodes; i++) {
        for (int j = 0; j < g->adj_count[i]; j++) in_degree[g->adj_list[i][j]]++;
    }

    int queue[MAX_NODES], head = 0, tail = 0, order_len = 0;
    for (int i = 0; i < g->num_nodes; i++) {
        if (in_degree[i] == 0) queue[tail++] = i; // no prerequisites — start here
    }

    while (head < tail) {
        int current = queue[head++];
        order[order_len++] = current;
        for (int i = 0; i < g->adj_count[current]; i++) {
            int next = g->adj_list[current][i];
            if (--in_degree[next] == 0) queue[tail++] = next;
        }
    }
    return order_len;
}

int main(void) {
    Graph gettingDressed = {0};
    int underwear = graph_add_node(&gettingDressed, "Underwear");
    int pants     = graph_add_node(&gettingDressed, "Pants");
    int belt      = graph_add_node(&gettingDressed, "Belt");
    int socks     = graph_add_node(&gettingDressed, "Socks");
    int shoes     = graph_add_node(&gettingDressed, "Shoes");

    graph_add_prereq(&gettingDressed, underwear, pants);
    graph_add_prereq(&gettingDressed, pants, belt);
    graph_add_prereq(&gettingDressed, socks, shoes);

    int order[MAX_NODES];
    int n = topological_sort(&gettingDressed, order);
    for (int i = 0; i < n; i++) printf("%s ", gettingDressed.names[order[i]]);
    printf("\n"); // e.g. Underwear Socks Pants Shoes Belt — a valid order respecting all rules
    return 0;
}

⏱️ Complexity: O(V + E) — visit every task and every "must happen before" rule once.

That's the full toolkit — 23 topics across three tiers, from egg-carton arrays to Dijkstra's shortest path. What follows isn't more to learn; it's the quick-reference for the moment that actually matters: staring at a new problem and recognizing which of these 23 tools it's asking for.