Rangkuman: Kahn's Algorithm

Topological Sort

1. Pengertian

Kahn's Algorithm adalah algoritma untuk melakukan **Topological Sort** pada sebuah Directed Acyclic Graph (DAG). Topological Sort adalah pengurutan linier dari simpul-simpul (vertices) sedemikian rupa sehingga untuk setiap sisi berarah $U \to V$, simpul $U$ selalu muncul sebelum simpul $V$ dalam urutan tersebut.

Algoritma ini tidak dapat diterapkan pada graf yang memiliki siklus, oleh karena itu hanya berlaku untuk DAG.

2. Konsep Dasar & Mekanisme

Kahn's Algorithm menggunakan konsep **"in-degree"** setiap simpul, yaitu jumlah sisi yang masuk ke simpul tersebut. Algoritma ini bekerja secara iteratif dengan mengidentifikasi dan memproses simpul-simpul yang tidak memiliki dependensi (in-degree 0).

Langkah-langkah Algoritma:

  1. Hitung in-degree untuk setiap simpul dalam graf.
  2. Inisialisasi sebuah antrian (queue) dan tambahkan semua simpul yang memiliki in-degree 0 ke dalam antrian tersebut.
  3. Inisialisasi daftar kosong untuk menyimpan hasil topological sort.
  4. Selama antrian tidak kosong:
    • Keluarkan (dequeue) sebuah simpul $U$ dari antrian.
    • Tambahkan $U$ ke daftar hasil topological sort.
    • Untuk setiap simpul $V$ yang merupakan tetangga dari $U$ (yaitu, ada sisi $U \to V$):
      • Kurangi in-degree dari $V$ sebesar 1.
      • Jika in-degree dari $V$ menjadi 0, tambahkan $V$ ke antrian.
  5. Setelah antrian kosong, jika jumlah simpul dalam daftar hasil sama dengan total simpul dalam graf, maka hasil tersebut adalah topological sort yang valid. Jika tidak, itu berarti graf memiliki siklus dan topological sort tidak mungkin dilakukan.

3. Contoh Ilustrasi

Graf berikut (DAG):


    1 ---> 2 ---> 3
    |      ^
    v      |
    4 ---> 5

Langkah 1: Hitung In-Degree Awal:

  • Node 1: in-degree = 0
  • Node 2: in-degree = 1 (dari 1)
  • Node 3: in-degree = 1 (dari 2)
  • Node 4: in-degree = 1 (dari 1)
  • Node 5: in-degree = 2 (dari 2, 4)

Langkah 2: Inisialisasi Antrian & Hasil:

  • Queue: [1]
  • Result: []

Langkah 4: Proses Iteratif:

  1. Keluarkan 1. Result: [1]. Tetangga 1: (2, 4).
    • in-degree(2) menjadi 0. Tambahkan 2 ke Queue.
    • in-degree(4) menjadi 0. Tambahkan 4 ke Queue.
    Queue: [2, 4]
  2. Keluarkan 2. Result: [1, 2]. Tetangga 2: (3, 5).
    • in-degree(3) menjadi 0. Tambahkan 3 ke Queue.
    • in-degree(5) menjadi 1.
    Queue: [4, 3]
  3. Keluarkan 4. Result: [1, 2, 4]. Tetangga 4: (5).
    • in-degree(5) menjadi 0. Tambahkan 5 ke Queue.
    Queue: [3, 5]
  4. Keluarkan 3. Result: [1, 2, 4, 3]. Tetangga 3: (tidak ada). Queue: [5]
  5. Keluarkan 5. Result: [1, 2, 4, 3, 5]. Tetangga 5: (tidak ada). Queue: []

Topological Sort: [1, 2, 4, 3, 5] (Ada kemungkinan urutan lain yang valid, seperti [1, 4, 2, 3, 5] dll.)

4. Pseudocode Algoritma


FUNCTION KahnTopologicalSort(graph):
    V = graph.NUM_VERTICES
    in_degree = CREATE ARRAY of size V, initialized to 0

    // Hitung in-degree untuk setiap simpul
    FOR EACH vertex U IN graph:
        FOR EACH neighbor V OF U:
            in_degree[V] = in_degree[V] + 1

    queue = new Queue()
    // Tambahkan semua simpul dengan in-degree 0 ke antrian
    FOR EACH vertex U IN graph:
        IF in_degree[U] == 0:
            queue.ENQUEUE(U)

    topological_order = []
    count_visited_nodes = 0

    WHILE queue IS NOT EMPTY:
        U = queue.DEQUEUE()
        topological_order.ADD(U)
        count_visited_nodes = count_visited_nodes + 1

        FOR EACH neighbor V OF U:
            in_degree[V] = in_degree[V] - 1
            IF in_degree[V] == 0:
                queue.ENQUEUE(V)

    IF count_visited_nodes != V:
        PRINT "Graf memiliki siklus, topological sort tidak mungkin."
        RETURN NULL // Atau error
    ELSE:
        RETURN topological_order

5. Kompleksitas Waktu & Ruang

  • Kompleksitas Waktu: $O(V + E)$, di mana $V$ adalah jumlah simpul dan $E$ adalah jumlah sisi.
    • Menghitung in-degree: $O(V + E)$.
    • Memproses simpul dan sisinya: Setiap simpul dan sisi akan dikunjungi dan diproses maksimal satu kali.
  • Kompleksitas Ruang: $O(V + E)$ untuk menyimpan graf (adjacency list), in-degree array, dan antrian.

6. Aplikasi

  • **Penjadwalan Tugas/Proyek:** Menentukan urutan tugas yang memiliki dependensi. Misalnya, dalam proses kompilasi kode (file A harus dikompilasi sebelum file B yang mengimpornya).
  • **Course Scheduling:** Menentukan urutan pengambilan mata kuliah di universitas berdasarkan prasyarat.
  • **Deadlock Detection:** Dalam sistem operasi atau basis data.
  • **Build Systems:** Mengurutkan modul yang perlu dibangun dalam urutan yang benar.
Kembali ke Materi Materi Selanjutnya