Topological Sorting

Seorang mahasiswa tidak bisa mengambil mata kuliah Algoritma Graph sebelum lulus Struktur Data. Tim build tidak bisa menjalankan test integration sebelum semua unit test lulus. Scheduler task tidak boleh mengeksekusi child process sebelum parent-nya selesai. Semua masalah ini memiliki struktur yang sama: sekumpulan task dengan relasi must-come-before, dan kita perlu urutan eksekusi yang valid. Inilah persoalan topological sorting — diterapkan khusus pada Directed Acyclic Graph (DAG). Pada Chapter ini kita akan membedah dua algoritma klasik: Kahn’s algorithm (berbasis in-degree + BFS) dan DFS post-order reversed — serta melihat kapan masing-masing lebih tepat.

Aturan: Urutan Konsisten dengan Edge #

Diberikan DAG G = (V, E) dengan edge u → v berarti “u harus muncul sebelum v”, sebuah urutan topologis adalah permutasi node sehingga untuk setiap edge (u, v), u muncul sebelum v dalam urutan tersebut.

Mekanisme 1: Kahn’s Algorithm (In-Degree + Queue) #

Ide Kahn: node dengan in-degree 0 aman diproses pertama (tidak ada prasyarat). Setelah diproses, hapus node tersebut dari graph secara konseptual — yaitu kurangi in-degree setiap tetangganya. Bila in-degree sebuah tetangga turun menjadi 0, node tersebut siap diproses berikutnya.

flowchart TD A["Hitung in-degree semua node"] --> B["Push node in-degree 0 ke queue"] B --> C{"Queue kosong?"} C -- Tidak --> D["Pop u, masukkan ke order"] D --> E["Untuk setiap edge u→v:<br/>in-degree[v]--<br/>bila 0, push v"] E --> C C -- Ya --> F{"|order| == |V|?"} F -- Ya --> G["Valid topo sort"] F -- Tidak --> H["Ada siklus"]

Mekanisme 2: DFS Post-Order Reversed #

Saat DFS menyelesaikan eksplorasi sebuah node (semua tetangga sudah dikunjungi), node tersebut ditambahkan ke list post-order. Karena DFS mengunjungi prasyarat (descendant) sebelum kembali ke node saat ini, urutan post-order menempatkan node setelah semua yang bergantung padanya. Membalik urutan ini menghasilkan urutan topologis.

Untuk mendeteksi siklus, gunakan tiga warna: WHITE (belum dikunjungi), GRAY (sedang diproses), BLACK (selesai). Edge ke node GRAY = siklus ditemukan.

Implementasi Kedua Algoritma #

cpp
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

class DAG {
    int n;
    std::vector<std::vector<int>> adj;
public:
    explicit DAG(int n) : n(n), adj(n) {}
    void add_edge(int u, int v) { adj[u].push_back(v); }

    // Kahn: BFS berbasis in-degree
    std::vector<int> topo_kahn() {
        std::vector<int> indeg(n, 0);
        for (int u = 0; u < n; ++u)
            for (int v : adj[u]) indeg[v]++;
        std::queue<int> q;
        for (int u = 0; u < n; ++u)
            if (indeg[u] == 0) q.push(u);
        std::vector<int> order;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            order.push_back(u);
            for (int v : adj[u]) {
                if (--indeg[v] == 0) q.push(v);
            }
        }
        return order;
    }

    // DFS post-order reversed
    std::vector<int> topo_dfs() {
        std::vector<int> color(n, 0); // 0=putih, 1=abu, 2=hitam
        std::vector<int> order;
        bool has_cycle = false;
        for (int u = 0; u < n; ++u) {
            if (color[u] == 0) {
                dfs(u, color, order, has_cycle);
            }
        }
        if (has_cycle) return {};
        std::reverse(order.begin(), order.end());
        return order;
    }

private:
    void dfs(int u, std::vector<int>& color, std::vector<int>& order, bool& has_cycle) {
        color[u] = 1; // abu-abu: sedang diproses
        for (int v : adj[u]) {
            if (color[v] == 1) { has_cycle = true; return; }
            if (color[v] == 0) dfs(v, color, order, has_cycle);
        }
        color[u] = 2; // hitam: selesai
        order.push_back(u); // post-order
    }
};

void print(const std::string& label, const std::vector<int>& v) {
    std::cout << label;
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';
}

int main() {
    // DAG mata kuliah:
    //   0(Algo Dasar) -> 1(Struktur Data)
    //   0 -> 2(Basis Data)
    //   1 -> 3(Algoritma Graph)
    //   2 -> 3
    //   3 -> 4(Tugas Akhir)
    DAG g(5);
    g.add_edge(0, 1);
    g.add_edge(0, 2);
    g.add_edge(1, 3);
    g.add_edge(2, 3);
    g.add_edge(3, 4);

    print("Kahn  : ", g.topo_kahn());
    print("DFS   : ", g.topo_dfs());
    return 0;
}

Output yang Dihasilkan:

text

Kahn  : 0 1 2 3 4 
DFS   : 0 2 1 3 4

Bedah Kode Baris-per-Baris #

std::vector<int> indeg(n, 0); for ... indeg[v]++: hitung in-degree setiap node dengan satu kali iterasi edge. Kompleksitas O(V + E).
for (int u = 0; u < n; ++u) if (indeg[u] == 0) q.push(u);: inisialisasi queue dengan semua node ber-in-degree 0. Tidak hanya satu sumber — Kahn mendukung multi-source secara natural.
order.push_back(u): node di-pop dari queue = aman dimasukkan ke urutan topologis karena semua prasyaratnya sudah diproses.
if (--indeg[v] == 0) q.push(v): kurangi in-degree v. Bila turun ke 0, semua prasyarat v sudah diproses — siap masuk antrian.
Hasil Kahn = 0 1 2 3 4: 0 dulu (in-deg 0). Setelah 0, in-degree 1 dan 2 turun jadi 0 → keduanya di-push. Queue FIFO memproses 1 sebelum 2.
std::vector<int> color(n, 0): tiga warna untuk deteksi siklus. WHITE=belum, GRAY=sedang diproses (di call stack), BLACK=selesai.
if (color[v] == 1) { has_cycle = true; return; }: edge ke node GRAY = edge kembali = siklus. DFS segera berhenti.
order.push_back(u) setelah loop: tambahkan node saat post-order (setelah semua descendant selesai). Inilah kunci yang membuat reverse menghasilkan urutan topologis.
std::reverse(order.begin(), order.end()): post-order dibalik = pre-order dengan urutan topologis. Node tanpa prasyarat (descendant terdalam) muncul lebih dulu setelah reverse.
Hasil DFS = 0 2 1 3 4: 0 dulu. DFS menyelam ke 2 (anak kanan adjacency list) sebelum 1, sehingga urutan berbeda dari Kahn — namun keduanya valid karena 1 dan 2 keduanya setelah 0 dan sebelum 3.

Komparasi Kahn vs DFS #

Aspek	Kahn’s Algorithm	DFS Post-Order
Pendekatan	In-degree + BFS	DFS + reverse
Deteksi siklus	`	order
Urutan node	Berdasarkan queue FIFO (deterministik)	Berdasarkan urutan adjacency list
Kompleksitas waktu	`O(V + E)`	`O(V + E)`
Kompleksitas ruang	`O(V)` (queue + indeg)	`O(V)` (call stack + color)
Lebih cocok untuk	Deteksi siklus sederhana, build system	Topo + SCC (DFS reusable)

Aplikasi Nyata #

Build system (Make, Gradle, Bazel): urutan kompilasi file sesuai dependency graph.
Course scheduling: urutan pengambilan mata kuliah sesuai prasyarat.
Pipeline task (Airflow, Prefect): task berjalan sesuai dependency yang didefinisikan.
Verilog simulation: urutan evaluasi gate sesuai dependensi sinyal.
Deadlock detection: cycle pada resource allocation graph = deadlock (bukan topo sort langsung, namun DFS cycle detection sama).

Kompleksitas #

Aspek	Kahn	DFS
Waktu	`O(V + E)`	`O(V + E)`
Ruang	`O(V)`	`O(V)` call stack
Deteksi siklus	Ya (cek panjang order)	Ya (cek edge ke GRAY)

Ringkasan #

Topological sort mengurutkan node DAG sesuai relasi must-come-before.
Kahn’s algorithm: BFS berbasis in-degree; node in-deg 0 diproses pertama, hapus secara konseptual, ulangi.
DFS post-order reversed: DFS biasa, tambahkan node ke list saat selesai, lalu balik urutannya.
Kedua algoritma memiliki kompleksitas O(V + E) dan dapat mendeteksi siklus.
Urutan hasil tidak unik — dua algoritma menghasilkan urutan berbeda yang sama-sama valid.
Untuk urutan lexicographic terkecil, gunakan min-heap pada Kahn.

Bab berikutnya beralih ke persoalan shortest path — gambaran umum algoritma-algoritma yang mencari jalur minimum pada graph berbobot.