Topological Sort mengurutkan node di Directed Acyclic Graph (DAG) sehingga setiap node muncul sebelum node yang bergantung padanya.

Kegunaan nyata (sangat relevan untuk web dev):

• npm/pnpm install — menentukan urutan instalasi package berdasarkan dependency
• Build system (webpack, vite) — urutan bundling module
• Database migration — urutan migrasi berdasarkan foreign key
• Task scheduling — urutan pekerjaan yang saling bergantung
• Course prerequisites — urutan mata kuliah (seperti di platform ini!)

Cara kerja (Kahn's Algorithm — BFS):

1. Hitung in-degree (jumlah edge masuk) setiap node
2. Masukkan node dengan in-degree 0 ke Queue
3. Proses Queue: ambil node, tambah ke hasil, kurangi in-degree tetangganya
4. Jika tetangga in-degree jadi 0, masukkan ke Queue
5. Jika hasil < jumlah node → ada cycle!

function topologicalSort(numNodes, edges) {
  // Build adjacency list dan in-degree
  const adj = Array.from({ length: numNodes }, () => []);
  const inDegree = new Array(numNodes).fill(0);

  for (const [from, to] of edges) {
    adj[from].push(to);
    inDegree[to]++;
  }

  // Start dengan node yang tidak punya dependency
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  // Cek cycle
  if (result.length !== numNodes) {
    return null; // Ada cycle! Tidak bisa topological sort
  }

  return result;
}

// Contoh: dependency package
// 0=react, 1=react-dom, 2=next, 3=tailwind, 4=app
const edges = [
  [0, 1],  // react → react-dom
  [0, 2],  // react → next
  [1, 2],  // react-dom → next
  [3, 4],  // tailwind → app
  [2, 4],  // next → app
];

topologicalSort(5, edges);
// → [0, 3, 1, 2, 4] atau [3, 0, 1, 2, 4]
// react & tailwind dulu (tidak ada dependency)
// lalu react-dom, next, dan terakhir app

Contoh praktis: Task Scheduler

function taskOrder(tasks, dependencies) {
  const map = new Map();
  tasks.forEach((t, i) => map.set(t, i));

  const edges = dependencies.map(([a, b]) => [map.get(a), map.get(b)]);
  const order = topologicalSort(tasks.length, edges);

  return order ? order.map(i => tasks[i]) : "Circular dependency detected!";
}

taskOrder(
  ["install", "build", "test", "deploy", "lint"],
  [["install", "build"], ["install", "lint"], ["build", "test"], ["lint", "test"], ["test", "deploy"]]
);
// → ["install", "lint", "build", "test", "deploy"]

Kompleksitas: O(V + E) — sangat efisien!

Catatan: Topological Sort hanya bisa dilakukan pada DAG (Directed Acyclic Graph). Jika ada cycle (A→B→C→A), tidak ada urutan yang valid.

🎭 Analogi sehari-hari: Pakai baju pagi-pagi. Kaos kaki sebelum sepatu. Celana sebelum sabuk. Kemeja sebelum dasi. Urutan tertentu wajib karena dependency. Topological sort = output urutan yang valid (kaos kaki bisa sebelum/sesudah celana, tapi sepatu harus di akhir).

💡 Mengapa wajib DAG (no cycle)? Cycle artinya ada masalah dependency: A butuh B, B butuh C, C butuh A. Gak ada urutan valid — circular dependency. npm/pnpm akan gagal install kalau dependency cyclic. Topological sort detect cycle sebagai bonus.

⚠️ Jebakan umum:

• Pakai di graph dengan cycle = hasil incomplete (cuma sort sebagian)
• Lupa cek result.length === numNodes untuk detect cycle
• Multiple valid orderings — output bisa beda dari expected, tapi tetap valid
• queue.shift() O(n) = pakai pointer-based queue untuk graph besar

🎯 Topological Sort kapan?

• Build dependency (npm, webpack, make, gradle)
• Database migration order
• Course prerequisites (matkul mana dulu)
• Task scheduling dengan dependency
• Compilation order (file mana di-compile dulu)
• Spreadsheet formulas evaluation order
• Course content sequencing (lesson dependency di platform pembelajaran)

🧪 Tebakan cepat: react → react-dom → next-app. Topological sort? react → react-dom → next-app (tidak ada urutan lain valid karena chain). Kalau react → A dan react → B independen, bisa A-B atau B-A.

TL;DR: Topological Sort = urutan node di DAG yang menghormati dependency. O(V+E) dengan Kahn (BFS in-degree). Wajib DAG. Foundation build system, package manager, scheduler.