DWI WAHYU ILAHI ANGKA

Apa itu Algoritma Kahn?

Algoritma Kahn adalah salah satu dari dua algoritma utama yang digunakan untuk melakukan pengurutan topologis (topological sort) pada sebuah Grafik Asiklik Terarah (Directed Acyclic Graph - DAG). Pengurutan topologis adalah susunan linier dari node-node sedemikian rupa sehingga untuk setiap sisi terarah (u, v) dalam grafik, node u selalu muncul sebelum node v dalam susunan. Penting untuk diingat bahwa pengurutan topologis hanya mungkin dilakukan pada DAG (grafik terarah tanpa siklus).

Algoritma ini sangat berguna dalam berbagai skenario di mana ada ketergantungan antar tugas atau item, misalnya:

Perencanaan tugas: Menentukan urutan tugas yang harus diselesaikan di mana beberapa tugas bergantung pada penyelesaian tugas lain (misalnya, membangun rumah: fondasi harus selesai sebelum dinding).
Manajemen dependensi paket: Mengidentifikasi urutan instalasi paket perangkat lunak di mana satu paket mungkin membutuhkan paket lain.
Penyelesaian kursus: Menentukan urutan mata kuliah yang harus diambil, di mana beberapa mata kuliah memiliki prasyarat.
Kompilasi kode: Menentukan urutan kompilasi file sumber yang saling bergantung.

Konsep Kunci: In-degree

Sebelum memahami cara kerja Algoritma Kahn, kita perlu mengenal konsep in-degree.In-degree (atau derajat masuk) dari sebuah node dalam grafik terarah adalah jumlah sisi yang masuk ke node tersebut.

Contoh:

Jika ada sisi A -> B dan C -> B, maka in-degree dari node B adalah 2.

Algoritma Kahn bekerja dengan prinsip dasar bahwa node dengan in-degree 0 tidak memiliki prasyarat dan oleh karena itu bisa menjadi titik awal dalam urutan topologis.

Cara Kerja Algoritma Kahn

Algoritma Kahn beroperasi secara iteratif, secara bertahap membangun urutan topologis. Berikut adalah langkah-langkah intinya:

Inisialisasi:
- Hitung in-degree untuk setiap node dalam grafik.
- Buat sebuah queue (antrian) dan tambahkan semua node yang memiliki in-degree 0 ke dalamnya. Node-node ini adalah yang pertama dalam urutan topologis.
Proses Iteratif:
- Sementara queue tidak kosong:
  - Ambil (dequeue) sebuah node dari bagian depan queue. Tambahkan node ini ke daftar hasil pengurutan topologis Anda.
  - Untuk setiap tetangga dari node yang baru saja diambil:
    - Kurangi in-degree tetangga tersebut sebanyak 1.
    - Jika in-degree tetangga tersebut menjadi 0, tambahkan tetangga tersebut ke queue.
Verifikasi (Opsional, tapi Penting):
- Setelah queue kosong, periksa apakah jumlah node dalam daftar hasil pengurutan topologis sama dengan total jumlah node dalam grafik. Jika tidak sama, ini berarti grafik tersebut mengandung siklus (bukan DAG), dan pengurutan topologis tidak mungkin dilakukan.

Contoh Permasalahan

Misalkan kita memiliki daftar mata kuliah dan prasyaratnya:

Mata Kuliah A: Tidak ada prasyarat
Mata Kuliah B: Prasyarat A
Mata Kuliah C: Prasyarat A
Mata Kuliah D: Prasyarat B, C
Mata Kuliah E: Prasyarat D

Grafik Terarah:

A --> B --> D --> E
|     ^
v     |
C ----|

Tujuan: Tentukan urutan mata kuliah yang harus diambil.

Langkah-langkah dengan Algoritma Kahn:

Inisialisasi In-degree:
- A: 0
- B: 1 (dari A)
- C: 1 (dari A)
- D: 2 (dari B, C)
- E: 1 (dari D)
Queue awal: [A] (karena in-degree A adalah 0)
Urutan Topologis: []
Proses Iteratif:
- Dequeue A. Urutan: [A]
  - Tetangga B: in-degree B menjadi 0. Enqueue B.
  - Tetangga C: in-degree C menjadi 0. Enqueue C.
  Queue: [B, C]
- Dequeue B. Urutan: [A, B]
  - Tetangga D: in-degree D menjadi 1 (dari 2).
  Queue: [C]
- Dequeue C. Urutan: [A, B, C]
  - Tetangga D: in-degree D menjadi 0 (dari 1). Enqueue D.
  Queue: [D]
- Dequeue D. Urutan: [A, B, C, D]
  - Tetangga E: in-degree E menjadi 0 (dari 1). Enqueue E.
  Queue: [E]
- Dequeue E. Urutan: [A, B, C, D, E]
  - Tidak ada tetangga.
  Queue: [] (Kosong)
Verifikasi:
- Jumlah node di hasil (5) sama dengan total node (5). Grafik adalah DAG.

Urutan Topologis Akhir: [A, B, C, D, E] (atau [A, C, B, D, E], karena B dan C bisa diambil secara paralel setelah A).

Implementasi Kode (C++)

Berikut adalah contoh implementasi Algoritma Kahn sederhana menggunakan C++. Dalam konteks Next.js, ini akan menjadi bagian dari backend atau layanan yang Anda panggil untuk mendapatkan urutan topologis.

#include <iostream>
#include <vector>
#include <queue>
#include <map> // Untuk mapping nama node ke indeks

// Fungsi untuk melakukan pengurutan topologis menggunakan Algoritma Kahn
std::vector<int> kahnTopologicalSort(int numNodes, const std::vector<std::vector<int>>& adj, std::vector<int>& inDegree) {
    std::queue<int> q;
    std::vector<int> result;

    // 1. Inisialisasi: Tambahkan semua node dengan in-degree 0 ke queue
    for (int i = 0; i < numNodes; ++i) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }

    // 2. Proses Iteratif
    int visitedNodes = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        result.push_back(u); // Tambahkan node ke hasil
        visitedNodes++;

        // Untuk setiap tetangga dari node u
        for (int v : adj[u]) {
            inDegree[v]--; // Kurangi in-degree tetangga
            // Jika in-degree tetangga menjadi 0, tambahkan ke queue
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }

    // 3. Verifikasi (opsional, tapi penting)
    if (visitedNodes != numNodes) {
        std::cout << "Grafik mengandung siklus! Pengurutan topologis tidak mungkin.\n";
        return {}; // Mengembalikan vektor kosong atau melempar error
    }

    return result;
}

int main() {
    int numNodes = 5; // A=0, B=1, C=2, D=3, E=4

    // Representasi graf menggunakan adjacency list
    std::vector<std::vector<int>> adj(numNodes);
    std::vector<int> inDegree(numNodes, 0);

    // Menambahkan sisi dan memperbarui in-degree
    // A -> B
    adj[0].push_back(1);
    inDegree[1]++;

    // A -> C
    adj[0].push_back(2);
    inDegree[2]++;

    // B -> D
    adj[1].push_back(3);
    inDegree[3]++;

    // C -> D
    adj[2].push_back(3);
    inDegree[3]++;

    // D -> E
    adj[3].push_back(4);
    inDegree[4]++;

    std::vector<int> topologicalOrder = kahnTopologicalSort(numNodes, adj, inDegree);

    if (!topologicalOrder.empty()) {
        std::cout << "Urutan Topologis (indeks node): ";
        for (int node : topologicalOrder) {
            std::cout << node << " ";
        }
        std::cout << "\n";
    }

    return 0;
}

Kelebihan dan Kekurangan

Kelebihan Algoritma Kahn:

Menjamin Pengurutan Topologis: Selama grafik adalah DAG, algoritma ini dijamin akan menemukan setidaknya satu urutan topologis yang valid.
Deteksi Siklus: Algoritma ini secara inheren dapat mendeteksi apakah sebuah grafik mengandung siklus. Jika jumlah node yang diproses tidak sama dengan total node, maka ada siklus.
Relatif Intuitif: Cara kerjanya berdasarkan prasyarat (in-degree) yang mudah dipahami.
Kompleksitas Waktu Efisien: Memiliki kompleksitas waktu O(V + E) di mana V adalah jumlah node dan E adalah jumlah sisi, membuatnya efisien untuk grafik besar.

Kekurangan Algoritma Kahn:

Hanya untuk DAG: Tidak dapat digunakan pada grafik yang mengandung siklus.
Bukan Algoritma Jalur Terpendek: Ini bukan algoritma untuk menemukan jalur terpendek (seperti Dijkstra), melainkan untuk menentukan urutan tugas.
Bisa Ada Banyak Solusi: Untuk grafik tertentu, mungkin ada lebih dari satu urutan topologis yang valid. Algoritma Kahn akan memberikan salah satu di antaranya.

Kesimpulan

Algoritma Kahn adalah metode yang elegan dan efisien untuk melakukan pengurutan topologis pada grafik asiklik terarah. Kemampuannya untuk secara otomatis mendeteksi siklus dan kompleksitas waktunya yang optimal menjadikannya pilihan yang sangat baik untuk masalah yang melibatkan dependensi tugas dan penjadwalan. Pemahaman tentang in-degree adalah kunci untuk menguasai algoritma ini, yang memiliki banyak aplikasi praktis di dunia nyata.