Topological sort menyusun daftar barang supaya tiap barang datang sesudah semua yang dia butuhkan. Contohnya package manager seperti npm: react-dom butuh react, jadi react harus dipasang lebih dulu. Yang dibutuhkan disebut dependency. Mirip memakai sepatu: kaus kaki dulu, baru sepatu.
🧪 Tebakan cepat:
abutuhb,bbutuhc, dancbutuha. Mana yang dipasang duluan? Tebak dulu, jawabannya ada di bagian "Kalau ada siklus".
Kahn: pasang yang gak menunggu apa-apa
Lima package dengan dependency-nya, ditulis [yang dibutuhkan, yang membutuhkan]: react sebelum react-dom, react sebelum next, react-dom sebelum next, tailwind sebelum app, next sebelum app.
Kuncinya in-degree: berapa dependency yang masih ditunggu sebuah package. Awalnya react 0, react-dom 1, next 2, tailwind 0, app 2. Package dengan in-degree 0 boleh langsung dipasang, jadi dia masuk antrian.
| Langkah | Dipasang | In-degree yang turun | Antrian sesudahnya |
|---|---|---|---|
| 1 | react |
react-dom jadi 0, next jadi 1 |
tailwind, react-dom |
| 2 | tailwind |
app jadi 1 |
react-dom |
| 3 | react-dom |
next jadi 0 |
next |
| 4 | next |
app jadi 0 |
app |
| 5 | app |
gak ada | kosong |
Urutannya: react, tailwind, react-dom, next, app. Cara ini namanya algoritma Kahn.
const deps = [
["react", "react-dom"],
["react", "next"],
["react-dom", "next"],
["tailwind", "app"],
["next", "app"],
];
function topoSort(nodes, deps) {
const inDegree = {};
const dependents = {};
for (const n of nodes) {
inDegree[n] = 0;
dependents[n] = [];
}
for (const [before, after] of deps) {
dependents[before].push(after);
inDegree[after]++;
}
const queue = nodes.filter((n) => inDegree[n] === 0);
const order = [];
while (queue.length > 0) {
const node = queue.shift();
order.push(node);
for (const m of dependents[node]) {
inDegree[m]--;
if (inDegree[m] === 0) queue.push(m);
}
}
return order.length === nodes.length ? order : null;
}
console.log(topoSort(["react", "react-dom", "next", "tailwind", "app"], deps));
// ["react", "tailwind", "react-dom", "next", "app"]
- Tiap pasangan
[before, after]artinyaafterbutuhbeforedipasang lebih dulu. dependents[before]mencatat siapa saja yang menunggubefore.inDegree[after]++menambah satu dependency yang ditungguafter.queue(antrian) mulai berisi package dengan in-degree 0.- Tiap putaran,
queue.shift()mengambil package paling depan dan memasangnya (order.push). Semua yang menunggunya turun in-degree-nya satu, dan yang jadi 0 masuk antrian. - Di akhir, kalau semua package terpasang,
orderdikembalikan. Kalau ada yang tertinggal, hasilnyanull.
Contoh kecil: C butuh A dan B, B butuh A. In-degree-nya A 0, B 1, C 2. Pasang A, lalu B, lalu C. Tiap package dan tiap dependency cuma diproses sekali, jadi kalau datanya dua kali lipat, waktunya kira-kira dua kali lipat juga.
Kalau ada siklus
Di tebakan tadi, a menunggu b, b menunggu c, dan c menunggu a. Semuanya saling menunggu, gak ada yang in-degree-nya 0, jadi antriannya kosong sejak awal. Gak ada urutan yang benar, dan function-nya mengembalikan null.
Makanya topological sort cuma bisa dipakai di DAG (directed acyclic graph): graph yang edge-nya punya arah (dari yang dibutuhkan ke yang membutuhkan) dan gak punya siklus.
⚠️ Jebakan yang sering ketemu
- Pasangannya terbalik. Di
[before, after], yang dibutuhkan ada di depan. Kalau dibaca terbalik, urutannya ikut terbalik. - Lupa mengecek siklus.
return ordersaja menghasilkan daftar yang kurang waktu ada siklus. Bandingkanorder.lengthdengan banyaknya package, dan kembalikannullkalau beda. - Mengira urutannya cuma satu. Di contoh,
tailwindjuga boleh dipasang paling awal. Topological sort memberi salah satu urutan yang benar.
TL;DR: Topological sort menyusun barang supaya tiap barang datang sesudah semua dependency-nya. Algoritma Kahn: hitung in-degree tiap package, masukkan yang 0 ke antrian, pasang satu per satu, kurangi in-degree yang menunggunya, dan masukkan yang jadi 0 ke antrian. Kalau ada yang gak pernah terpasang, ada siklus: kembalikan null. Topological sort cuma bisa di DAG. C butuh A dan B, B butuh A: urutannya A, B, C.
