🔄Kahn's Algorithm

Kahn’s Algorithm adalah algoritma yang digunakan untuk melakukan topological sort pada graf berarah tanpa siklus (DAG) yang diperkenalkan oleh Arthur B. Kahn pada tahun 1962.

🎯 Tujuan Utama

Menyusun simpul-simpul dalam urutan sedemikian rupa sehingga jika ada edge dari simpul U ke simpul V, maka U muncul sebelum V dalam urutan hasil.

🌟 Aplikasi Praktis

📅 Penjadwalan tugas dengan dependensi 💻 Kompilasi kode dan build system 🏗️ Sistem build untuk proyek software 🔗 Dependency management antar modul 📊 Project management dan task scheduling

🧩 Konsep Utama

📊 Graf Berarah (Directed Graph) Directed Acyclic Graph (DAG) adalah graf berarah tanpa siklus yang digunakan untuk memodelkan hubungan dependensi atau urutan tugas.

✨ Karakteristik DAG:

• 🔄 Berarah: Setiap edge memiliki arah tertentu
• 🚫 Tanpa Siklus: Tidak ada jalur yang kembali ke node asal
• 📈 Hierarkis: Menunjukkan struktur ketergantungan
• ⚡ Efisien: Representasi kompleks tanpa perulangan

🔄 Acyclic (Tanpa Siklus) Acyclic berarti graf tidak boleh memiliki rangkaian edge yang membentuk loop (jalur berulang ke node yang sama).

• ✅ Topological sort hanya mungkin pada graf tanpa siklus
• ❌ Jika ada siklus, node akan saling bergantung secara circular
• 🔍 Tidak bisa diurutkan secara linier jika terdapat siklus

📥 In-degree In-degree adalah jumlah edge yang masuk ke suatu node, mengukur seberapa banyak dependensi yang dimiliki node tersebut. Fungsi dalam Kahn’s Algorithm:

• 📊 Mengukur dependensi node
• 🎯 Menentukan urutan eksekusi
• 🔍 Mendeteksi siklus dengan memantau node yang tidak pernah mencapai in-degree = 0

📋 Topological Sort Topological Sort adalah metode pengurutan node dalam DAG berdasarkan ketergantungan hierarkis.

🚀 Langkah Detail

• Step 1: 🔢 Hitung In-degree

Hitung jumlah edge masuk untuk setiap node

Inisialisasi counter untuk setiap node

• Step 2: 📥 Inisialisasi Queue

Masukkan semua node dengan in-degree = 0 ke dalam queue

Node-node ini tidak memiliki dependensi

• Step 3: 🔄 Proses Iteratif Selama queue tidak kosong:

🎯 Keluarkan node dari queue (u)

➕ Masukkan u ke dalam hasil topological sort

🔄 Untuk setiap tetangga v dari u:

➖ Kurangi in-degree[v] sebanyak 1

🔍 Jika in-degree[v] = 0, masukkan v ke queue

• Step 4: ✅ Validasi Hasil

📊 Jika jumlah node dalam hasil ≠ jumlah node di graf

⚠️ Maka graf memiliki siklus (tidak valid untuk topological sort)

🚀 Aplikasi Dunia Nyata

• 📅 Project Management: Task scheduling dengan dependensi
• 💻 Software Development: Build systems dan compilation order
• 📚 Academic: Course prerequisite planning
• 🏗️ Manufacturing: Production pipeline optimization
• 🔗 System Design: Module dependency resolution