Topological Sorting Berbasis Decrease and Conquer: Implementasi Algoritma Kahn Menggunakan Java dan Analisis Kompleksitas Waktu

Muhammad Hasbi (STMIK KAPUTAMA)

Jurnal Inovasi Informatika dan Bisnis Digital (JIIBD)
Vol 1 No 3 (2026): Juli 2026

Permasalahan pengurutan berdasarkan ketergantungan merupakan tantangan umum dalam rekayasa perangkat lunak, penjadwalan akademik, dan kompilasi program. Jurnal ini menyajikan kajian komprehensif tentang Topological Sorting menggunakan paradigma Decrease and Conquer melalui Algoritma Kahn. Penelitian dimulai dari fondasi teoretis Directed Acyclic Graph (DAG), kemudian menguraikan mekanisme kerja algoritma secara bertahap, menganalisis kompleksitas waktu O(V+E), dan mengimplementasikannya dalam bahasa Java. Pengujian dilakukan pada dua skenario: graf normal dan graf bersiklus. Hasil menunjukkan bahwa algoritma berhasil menghasilkan urutan topologis yang valid dan mampu mendeteksi siklus secara otomatis. Paradigma Decrease and Conquer terbukti efektif karena menyederhanakan persoalan kompleks menjadi langkah-langkah yang dapat dieksekusi secara linear.