GraphsLanjutFase E–FE1E5

KRUSKAL MAZE

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.

Example use case

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

Syllabus

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

Objectives

·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

How It Works

·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

Prerequisites

·Graf
·Union-Find (disjoint set)

Real-World Uses

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

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