GrafLanjutFase E–FE1E5

Maze Kruskal

Algoritma ini membangun labirin acak yang tetap terhubung menggunakan Kruskal dengan struktur Union-Find. Dinding diproses dalam urutan acak; sebuah dinding dibuka hanya jika dua sel di kedua sisinya belum berada dalam himpunan yang sama, lalu kedua himpunan digabung. Visualisasi menampilkan jumlah grup yang menyusut dari 22 menjadi 1 sampai seluruh sel menyatu jadi satu graf terhubung.

Contoh kasus

Pembuatan level labirin acak yang selalu bisa diselesaikan pada game maze atau prosedur generasi peta.

Silabus

Kruskal membangun labirin terhubung dengan membuka dinding acak hanya jika kedua sisinya belum tergabung, dicek cepat lewat Union-Find.

Tujuan Belajar

·Memahami cara Union-Find mengecek dua sel sudah tergabung atau belum
·Menjelaskan kenapa dinding dibuka hanya bila menyatukan dua grup berbeda
·Menerapkan Kruskal untuk membuat labirin acak yang selalu bisa dilewati

Cara Kerja

·Anggap tiap sel sebagai grup tersendiri di awal
·Acak urutan semua dinding yang mungkin dibuka
·Untuk tiap dinding, cek apakah dua sel di sisinya sudah satu grup
·Bila beda grup, buka dinding dan gabungkan (union) kedua grup
·Ulangi sampai semua sel menyatu jadi satu graf terhubung

Prasyarat

·Graf
·Union-Find (disjoint set)

Contoh Nyata

·Membuat level labirin acak yang dijamin bisa diselesaikan di game
·Prosedur generasi peta pada game petualangan
·Merancang jaringan kabel termurah yang menghubungkan semua titik

Kompleksitas O(E log E) dengan Union-Find hampir konstan per operasi