Topological Sort
Terakhir diperbarui
Topological sort pada directed acyclic graph (DAG) adalah urutan linear dari node-node-nya sehingga untuk setiap edge u → v, u muncul sebelum v. Topological sort menjawab pertanyaan seperti "dalam urutan apa tugas-tugas ini bisa dijalankan agar setiap prasyaratnya selesai lebih dulu?" Tekan Putar di atas untuk melihat algoritma Kahn melepaskan node satu per satu dalam urutan yang valid.
Algoritma Kahn berulang kali mengambil node yang tidak punya edge masuk tersisa (indegree 0), menambahkannya ke urutan, lalu menghapus edge keluarnya, yang mungkin membuat node lain menjadi indegree 0. Algoritma ini hanya bekerja pada DAG: jika ada siklus, beberapa node tidak pernah mencapai indegree 0 dan tidak ada urutan yang valid. Algoritma ini berjalan dalam waktu O(V + E).
Kompleksitas waktu dan ruang
| Ukuran | Kompleksitas | Catatan |
|---|---|---|
| Waktu | O(V + E) | Setiap node dikeluarkan sekali, setiap edge dihapus sekali |
| Ruang | O(V) | Hitungan indegree + himpunan siap + urutan |
| Membutuhkan | Sebuah DAG | Siklus tidak punya urutan topologis |
| Hasil | Tidak unik | Bisa ada banyak urutan yang valid |
Langkah demi langkah (algoritma Kahn)
| Langkah | Apa yang terjadi |
|---|---|
| 1 | Hitung indegree (jumlah edge masuk) setiap node. |
| 2 | Kumpulkan semua node dengan indegree 0 ke dalam himpunan siap. |
| 3 | Ambil satu node yang siap, tambahkan ke urutan output. |
| 4 | Kurangi indegree setiap node penerusnya. |
| 5 | Setiap node penerus yang mencapai indegree 0 masuk ke himpunan siap. |
| 6 | Ulangi sampai himpunan siap kosong. |
Contoh penerapan
Mengurutkan DAG dengan edge A→C, B→C, C→D, C→E, D→F, E→F (indegree awal A:0 B:0 C:2 D:1 E:1 F:2):
| Langkah | Himpunan siap | Urutan | Aksi |
|---|---|---|---|
| 0 | {A, B} | [] | A dan B dimulai dengan indegree 0, jadi keduanya siap. |
| 1 | {B} | [A] | Keluarkan A; edge A→C menurunkan indegree C dari 2 → 1. |
| 2 | {C} | [A, B] | Keluarkan B; edge B→C menurunkan C dari 1 → 0, jadi C menjadi siap. |
| 3 | {D, E} | [A, B, C] | Keluarkan C; edge C→D dan C→E menurunkan D dan E menjadi 0, keduanya menjadi siap. |
| 4 | {E} | [A, B, C, D] | Keluarkan D; edge D→F menurunkan indegree F dari 2 → 1. |
| 5 | {F} | [A, B, C, D, E] | Keluarkan E; edge E→F menurunkan F dari 1 → 0, jadi F menjadi siap. |
| 6 | {} | [A, B, C, D, E, F] | Keluarkan F; himpunan siap kosong dan keenam node sudah terurut: selesai. |
Kapan memakai topological sort
| Pakai saat | Hindari saat |
|---|---|
| Kamu butuh urutan yang menghormati ketergantungan (langkah build, instalasi paket, prasyarat mata kuliah). | Grafnya tidak berarah: urutan topologis hanya terdefinisi untuk graf berarah. |
| Grafnya adalah DAG dan kamu ingin satu urutan linear yang valid, apa pun itu. | Grafnya mungkin berisi siklus dan kamu tetap butuh urutan total (urutan itu tidak ada). |
| Kamu ingin mendeteksi siklus dengan murah: topological sort yang gagal membuktikan ada siklus. | Kamu butuh urutan terpendek atau optimal berdasarkan bobot tertentu; topological sort biasa mengabaikan bobot. |
Kamu akan memproses urutannya sekali dalam O(V + E). | Edge terus berubah dan kamu harus mengurutkan ulang di setiap perubahan, di mana struktur inkremental lebih cocok. |
Kode Topological Sort
Implementasi Topological Sort yang rapi dan siap dijalankan dalam Python, JavaScript, Java, C++, C. Pilih bahasa, salin kodenya, atau buka langsung di Coddy Playground.
Kode Topological Sort dalam Python
Python
1from collections import deque2
3
4def topological_sort(graph):5 # Kahn's algorithm: repeatedly remove nodes with no incoming edges6 in_degree = {node: 0 for node in graph}7 for node in graph:8 for neighbor in graph[node]:9 in_degree[neighbor] += 110 queue = deque(node for node in graph if in_degree[node] == 0)11 order = []12 while queue:13 node = queue.popleft()14 order.append(node)15 for neighbor in graph[node]:16 in_degree[neighbor] -= 117 if in_degree[neighbor] == 0:18 queue.append(neighbor)19 if len(order) != len(graph):20 raise ValueError("Graph has a cycle, no topological order")21 return order22
23
24graph = {25 "shirt": ["tie", "jacket"],26 "tie": ["jacket"],27 "pants": ["shoes", "jacket"],28 "socks": ["shoes"],29 "shoes": [],30 "jacket": [],31}32
33print(" -> ".join(topological_sort(graph)))Kode Topological Sort dalam JavaScript
JavaScript
1const graph = {2 A: ["C"],3 B: ["C", "D"],4 C: ["E"],5 D: ["F"],6 E: ["F"],7 F: [],8};9
10// Kahn algorithm: repeatedly take a node with no incoming edges11function topologicalSort() {12 const inDegree = {};13 for (const node in graph) inDegree[node] = 0;14 for (const node in graph) {15 for (const next of graph[node]) inDegree[next]++;16 }17 const queue = Object.keys(inDegree).filter((n) => inDegree[n] === 0);18 const order = [];19 while (queue.length > 0) {20 const node = queue.shift();21 order.push(node);22 for (const next of graph[node]) {23 if (--inDegree[next] === 0) queue.push(next);24 }25 }26 if (order.length !== Object.keys(graph).length) {27 throw new Error("Graph has a cycle");28 }29 return order;30}31
32console.log("Topological order:", topologicalSort().join(" -> "));Kode Topological Sort dalam Java
Java
1import java.util.ArrayDeque;2import java.util.List;3import java.util.Queue;4
5public class Main {6 public static void main(String[] args) {7 int n = 6;8 // DAG: an edge u -> v means u must come before v9 List<List<Integer>> adj = List.of(10 List.of(2),11 List.of(2, 3),12 List.of(4),13 List.of(4),14 List.of(5),15 List.of()16 );17 int[] inDegree = new int[n];18 for (List<Integer> next : adj) {19 for (int v : next) inDegree[v]++;20 }21
22 // Kahn: start from every node with no prerequisites23 Queue<Integer> queue = new ArrayDeque<>();24 for (int i = 0; i < n; i++) {25 if (inDegree[i] == 0) queue.add(i);26 }27
28 StringBuilder order = new StringBuilder("Topological order:");29 while (!queue.isEmpty()) {30 int node = queue.poll();31 order.append(" ").append(node);32 for (int next : adj.get(node)) {33 if (--inDegree[next] == 0) queue.add(next);34 }35 }36 System.out.println(order);37 }38}Kode Topological Sort dalam C++
C++
1#include <iostream>2#include <queue>3#include <vector>4
5int main() {6 // Directed acyclic graph: adj[u] lists nodes that depend on u7 std::vector<std::vector<int>> adj = {8 {}, // 09 {}, // 110 {3}, // 2 -> 311 {1}, // 3 -> 112 {0, 1}, // 4 -> 0, 113 {0, 2}, // 5 -> 0, 214 };15 int n = static_cast<int>(adj.size());16 std::vector<int> inDegree(n, 0);17 for (const auto& neighbors : adj) {18 for (int v : neighbors) ++inDegree[v];19 }20 // Kahn's algorithm: start from nodes with no incoming edges21 std::queue<int> ready;22 for (int u = 0; u < n; ++u) {23 if (inDegree[u] == 0) ready.push(u);24 }25 std::cout << "Topological order: ";26 while (!ready.empty()) {27 int u = ready.front();28 ready.pop();29 std::cout << u << " ";30 // Removing u unlocks neighbors whose in-degree drops to 031 for (int v : adj[u]) {32 if (--inDegree[v] == 0) ready.push(v);33 }34 }35 std::cout << "\n";36 return 0;37}Kode Topological Sort dalam C
C
1#include <stdio.h>2
3#define N 64
5int main(void) {6 // Directed acyclic graph: adj[u][v] = 1 means an edge u -> v7 int adj[N][N] = {0};8 adj[2][3] = 1;9 adj[3][1] = 1;10 adj[4][0] = 1;11 adj[4][1] = 1;12 adj[5][0] = 1;13 adj[5][2] = 1;14 int inDegree[N] = {0};15 for (int u = 0; u < N; u++) {16 for (int v = 0; v < N; v++) inDegree[v] += adj[u][v];17 }18 // Kahn's algorithm: start from nodes with no incoming edges19 int queue[N];20 int head = 0, tail = 0;21 for (int u = 0; u < N; u++) {22 if (inDegree[u] == 0) queue[tail++] = u;23 }24 printf("Topological order: ");25 while (head < tail) {26 int u = queue[head++];27 printf("%d ", u);28 // Removing u unlocks neighbors whose in-degree drops to 029 for (int v = 0; v < N; v++) {30 if (adj[u][v] && --inDegree[v] == 0) queue[tail++] = v;31 }32 }33 printf("\n");34 return 0;35}FAQ Topological Sort
Untuk apa topological sort dipakai?
Topological sort mengurutkan tugas sehingga setiap ketergantungan muncul sebelum hal yang membutuhkannya. Contoh penggunaan nyatanya antara lain build system dan package manager (meng-compile dependensi lebih dulu), penjadwalan mata kuliah dengan prasyarat, dan urutan evaluasi rumus spreadsheet.
Berapa kompleksitas waktu topological sort?
Algoritma Kahn maupun pendekatan berbasis DFS berjalan dalam waktu
O(V + E), karena setiap node diproses sekali dan setiap edge diperiksa sekali. Keduanya memakai ruang tambahan O(V).Mengapa topological sort membutuhkan DAG?
Siklus berarah menciptakan kontradiksi: jika
a harus muncul sebelum b dan b harus muncul sebelum a, tidak ada urutan linear yang bisa memenuhi keduanya. Jadi, urutan topologis ada jika dan hanya jika grafnya adalah directed acyclic graph. Algoritma Kahn mendeteksi siklus saat algoritma itu selesai sebelum mengeluarkan setiap node.Apa perbedaan algoritma Kahn dan topological sort berbasis DFS?
Algoritma Kahn bersifat iteratif dan mirip BFS: algoritma ini berulang kali menghapus node dengan indegree 0, sehingga deteksi siklus dan urutannya benar-benar eksplisit. Pendekatan DFS mengunjungi node secara rekursif dan menaruh setiap node di depan urutan saat rekursinya selesai, sehingga menghasilkan kebalikan dari urutan waktu selesainya. Keduanya bernilai
O(V + E); algoritma Kahn menghindari rekursi yang dalam dan secara alami menampilkan himpunan siap, sedangkan DFS sering lebih singkat ditulis.Kapan sebaiknya memakai topological sort, bukan pengurutan biasa?
Pakai topological sort saat urutannya ditentukan oleh ketergantungan antar-item, bukan oleh key yang bisa dibandingkan. Pengurutan berbasis perbandingan biasa seperti mergesort
O(n log n) mengurutkan berdasarkan nilai; topological sort mengurutkan berdasarkan edge "harus muncul sebelum", dan tidak seperti pengurutan berbasis perbandingan, topological sort bisa menghasilkan banyak jawaban yang valid untuk input yang sama.Apakah hasil topological sort selalu unik?
Biasanya tidak. Setiap kali ada dua node atau lebih yang siap (indegree 0) pada saat yang sama, kamu boleh mengeluarkannya dalam urutan apa pun, jadi kebanyakan DAG punya beberapa urutan topologis yang valid. Urutannya hanya unik jika di setiap langkah ada tepat satu node yang siap, yaitu saat DAG membentuk satu rantai tunggal (Hamiltonian path).
Sumber terkait
Visualisasi lainnya
