GraphsMenengahFase D–FE1E5

TOPOLOGICAL SORT

Topological Sort mengurutkan simpul pada graf berarah tanpa siklus (DAG) sehingga setiap prasyarat muncul sebelum yang membutuhkannya. Algoritma Kahn: ambil simpul tanpa prasyarat (in-degree 0), keluarkan, hapus panah keluarnya, ulangi. Hasilnya urutan yang valid.

Example use case

Menyusun urutan mata pelajaran: Matematika Dasar harus sebelum Fisika, Fisika sebelum materi lanjutannya.

Syllabus

Topological Sort mengurutkan simpul pada graf berarah tanpa siklus (DAG) sehingga setiap prasyarat selalu muncul sebelum yang membutuhkannya.

Objectives

·Memahami arti DAG dan konsep prasyarat antar simpul
·Menjelaskan cara kerja algoritma Kahn lewat in-degree
·Menerapkan urutan topologis untuk menyusun langkah bertahap

How It Works

·Hitung in-degree tiap simpul (berapa panah masuk = jumlah prasyarat)
·Ambil semua simpul dengan in-degree 0 (tanpa prasyarat)
·Keluarkan simpul itu ke hasil urutan, hapus panah keluarnya
·Kurangi in-degree tetangga; yang jadi 0 masuk antrean berikutnya
·Ulangi sampai semua simpul terurut menjadi rangkaian yang valid

Prerequisites

·Graf berarah (directed graph)
·Antrian (queue)

Real-World Uses

·Menyusun urutan mata pelajaran: Matematika Dasar sebelum Fisika
·Build tool menentukan file mana dikompilasi lebih dulu
·Urutan misi di game yang mengunci quest lanjutan sampai prasyarat selesai

Complexity O(V + E)