To porządek wierzchołków taki, że każda krawędź u→v prowadzi od wcześniejszego do późniejszego. Istnieje tylko dla DAG (grafu skierowanego acyklicznego); cykl oznacza brak poprawnej kolejności.
function topoSort(n: number, edges: Array<[number, number]>) {
const indeg = Array(n).fill(0);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
indeg[v]++;
}
const q: number[] = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
const order: number[] = [];
while (q.length) {
const u = q.shift()!;
order.push(u);
for (const v of g[u]) {
indeg[v]--;
if (indeg[v] === 0) q.push(v);
}
}
return order.length === n ? order : null; // null => cycle
}Sortowanie topologiczne to kolejność w grafie skierowanym zgodna z zależnościami: wymagania przed zależnymi. Istnieje wtedy i tylko wtedy, gdy nie ma cyklu skierowanego.
Dwa standardowe sposoby: