KAHN'S ALGORITHM
Kahn’s Algorithm
Dokumen ini membahas Kahn’s Algorithm, yaitu algoritma berbasis Breadth-First Search (BFS) untuk melakukan penyusunan topologis (topological sorting) pada graf berarah tanpa siklus (DAG - Directed Acyclic Graph).
Definisi
Kahn’s Algorithm adalah pendekatan sistematis untuk menyusun simpul dalam urutan linear berdasarkan ketergantungan arah dalam sebuah graf DAG. Apabila terdapat sisi $u \rightarrow v$, maka simpul u harus muncul sebelum simpul v dalam urutan topologis.
Kegunaan
Kahn’s Algorithm digunakan dalam berbagai konteks yang melibatkan urutan ketergantungan, seperti:
- Penjadwalan Tugas dengan dependensi prasyarat
- Kompilasi Program, memastikan file dikompilasi sesuai urutan yang benar
- Deteksi Siklus pada graf terarah
Cara Kerja Algoritma
- Hitung in-degree (jumlah sisi masuk) untuk setiap simpul.
- Masukkan semua simpul dengan in-degree = 0 ke dalam queue.
- Proses queue:
- Ambil simpul dari depan queue
- Tambahkan simpul ke urutan topologis
- Kurangi in-degree dari setiap tetangga simpul
- Jika in-degree menjadi 0, masukkan ke dalam queue
- Jika seluruh simpul dapat diproses, graf tidak memiliki siklus. Jika tidak, berarti terdapat siklus.
Contoh Kasus
Contoh 1: Penjadwalan Mata Kuliah
1
A → C ← B → D ← C
In-degree:
- A, B: 0
- C: 2
- D: 1
Urutan valid: A, B, C, D atau B, A, C, D
Contoh 2: Ketergantungan Proyek
1
2
F → A → D → C
F → B → D
Urutan valid: F, A, B, D, C, E atau F, B, A, D, C, E
Implementasi dalam C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <unordered_map>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
unordered_map<char, vector<char>> graph;
unordered_map<char, int> in_degree;
set<char> vertices;
void allTopologicalSorts(vector<char> &res, vector<bool> &visited) {
bool flag = false;
for (char v : vertices) {
if (!visited[v] && in_degree[v] == 0) {
flag = true;
visited[v] = true;
res.push_back(v);
for (char neighbor : graph[v]) in_degree[neighbor]--;
allTopologicalSorts(res, visited);
visited[v] = false;
res.pop_back();
for (char neighbor : graph[v]) in_degree[neighbor]++;
}
}
if (!flag && res.size() == vertices.size()) {
for (char c : res) cout << c << " ";
cout << endl;
}
}
int main() {
int E;
cout << "Masukkan jumlah edge: ";
cin >> E;
cout << "Masukkan sisi (format: A B):\n";
for (int i = 0; i < E; ++i) {
char u, v;
cin >> u >> v;
graph[u].push_back(v);
in_degree[v]++;
vertices.insert(u);
vertices.insert(v);
}
for (char v : vertices)
if (in_degree.find(v) == in_degree.end())
in_degree[v] = 0;
vector<char> res;
vector<bool> visited(256, false);
cout << "\nSemua urutan topologis valid:\n";
allTopologicalSorts(res, visited);
return 0;
}
Kelebihan dan Kekurangan
Kelebihan:
- Kompleksitas waktu: O(V + E)
- Dapat mendeteksi siklus
- Efisien untuk menyusun urutan berdasarkan ketergantungan
Kekurangan:
- Tidak dapat digunakan pada graf yang memiliki siklus
- Bisa menghasilkan banyak urutan yang valid
- Memerlukan struktur data tambahan seperti map dan queue
Kesimpulan
Kahn’s Algorithm merupakan pendekatan efisien dan sederhana untuk menyusun urutan simpul dalam graf DAG. Dengan menggunakan konsep in-degree dan BFS, algoritma ini memberikan solusi yang kuat untuk berbagai kebutuhan penyusunan ketergantungan.