Topological Sorting Berbasis Decrease and Conquer: Implementasi Algoritma Kahn Menggunakan Java dan Analisis Kompleksitas Waktu
DOI:
https://doi.org/10.59934/jiibd.v1i3.2531Kata Kunci:
Topological Sorting, Decrease and Conquer, Algoritma Kahn, DAG, Kompleksitas Waktu, JavaAbstrak
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.
Unduhan
Referensi
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Kahn, A. B. (1962). Topological sorting of large networks. Communications of the ACM, 5(11), 558–562.
Levitin, A. (2012). Introduction to The Design and Analysis of Algorithms (3rd ed.). Pearson Education.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley Professional.
GeeksforGeeks. (2024). Topological Sorting. https://www.geeksforgeeks.org/topological-sorting/
Kleinberg, J., & Tardos, E. (2005). Algorithm Design. Addison-Wesley.
npm Documentation. (2024). Dependency resolution. https://docs.npmjs.com/cli/v10/configuring-npm/package-json#dependencies
Apache Airflow. (2024). DAGs and Task Dependencies. https://airflow.apache.org/docs/
Topological Sorting: Implementasi Decrease and Conquer
Unduhan
Diterbitkan
Cara Mengutip
Terbitan
Bagian
Lisensi
Hak Cipta (c) 2026 Jurnal Inovasi Informatika dan Bisnis Digital (JIIBD)
Artikel ini berlisensiCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
