Motivasi

Urutan topologis hanya ada jika graf tidak memiliki siklus. Kita menyusunnya dengan algoritma Kahn, yang berulang kali menghapus simpul yang tidak memiliki sisi masuk tersisa.

Mengapa mempelajari Pengurutan Topologis?

• Pengurutan dengan batasan: sistem build, penjadwalan tugas, prasyarat kursus, dan penghitungan ulang spreadsheet semuanya mengandalkannya.
• Deteksi siklus: jika kamu tidak dapat mengurutkan setiap simpul, graf tersebut pasti mengandung siklus.
• Dasar untuk algoritma DAG: lintasan terpendek dan terpanjang dalam DAG dihitung dalam urutan topologis.

Banyak urutan valid yang mungkin ada. Untuk mendapatkan satu jawaban yang dapat diprediksi, kita selalu menghapus simpul bernomor paling kecil yang memiliki derajat masuk 0.