Generator Labirin Algoritma Kruskal

Algoritma Kruskal adalah algoritma pohon rentang minimum yang dapat diadaptasi untuk pembuatan labirin. Algoritma ini sangat efektif untuk membuat labirin yang sempurna. Alternatif untuk algoritma Kruskal adalah algoritma Prim, yang juga merupakan algoritma pohon rentang minimum, tetapi karena keduanya menghasilkan labirin yang identik dan kecepatan lari Kruskal lebih cepat, saya tidak perlu repot-repot menerapkan algoritma Prim.

Labirin yang sempurna adalah labirin yang hanya memiliki satu jalan dari titik mana pun di dalam labirin ke titik lainnya. Itu berarti Anda tidak bisa berputar-putar, tetapi Anda akan sering menemui jalan buntu, memaksa Anda untuk berbalik dan kembali.

Peta labirin yang dibuat di sini termasuk versi default tanpa posisi awal dan akhir, sehingga Anda dapat menentukannya sendiri: akan ada solusi dari titik mana pun di dalam labirin ke titik lainnya. Jika Anda menginginkan inspirasi, Anda dapat mengaktifkan posisi awal dan akhir yang disarankan - dan bahkan melihat solusi di antara keduanya.

Tentang Algoritma Kruskal

Algoritma Kruskal diciptakan oleh Joseph Bernard Kruskal, Jr., seorang matematikawan, ahli statistik, dan ilmuwan komputer Amerika. Ia pertama kali mendeskripsikan algoritma tersebut pada tahun 1956 dalam makalahnya "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

Algoritma ini dirancang untuk menemukan pohon rentang minimum (MST) dari suatu grafik, memastikan bahwa semua simpul terhubung dengan bobot tepi total seminimal mungkin sambil menghindari siklus.

Cara Kerja Algoritma Kruskal untuk Pembuatan Labirin

Langkah 1: Inisialisasi

• Perlakukan setiap sel dalam labirin sebagai satu set terpisah (komponen unik).
• Daftarkan semua dinding di antara sel yang berdekatan sebagai tepi potensial.

Langkah 2: Sortir Dinding

• Acak atau urutkan dinding secara acak. Jika menerapkannya sebagai algoritma Kruskal yang sebenarnya, urutkan dinding dalam urutan acak (karena pembuatan labirin tidak memerlukan bobot).

Langkah 3: Proses Dinding

• Beriterasi melalui dinding yang diacak.
• Jika dua sel yang dibagi oleh dinding termasuk dalam set yang berbeda (yakni, keduanya belum terhubung dalam labirin), singkirkan dinding dan gabungkan set tersebut.
• Jika sudah berada dalam set yang sama, lewati dinding (untuk menghindari siklus).

Langkah 4: Lanjutkan Sampai Selesai

• Ulangi proses ini hingga semua sel terhubung, membentuk pohon rentang tunggal.
• Pada akhirnya, setiap sel terhubung satu sama lain tanpa lingkaran atau bagian yang terisolasi.

Karena algoritma Kruskal bergantung pada penggabungan himpunan, algoritma ini dapat dioptimalkan dengan menggunakan algoritma Union-Find, yang menyediakan cara yang efisien untuk melacak sel yang terhubung selama pembuatan labirin. Anda dapat melihat implementasi PHP saya dari algoritma Union-Find di sini: Algoritma Disjoint Set (Union-Find) dalam PHP