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 algoritma Kruskal berjalan lebih cepat, saya tidak repot-repot mengimplementasikan 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 menjelaskan algoritma tersebut pada tahun 1956 dalam makalahnya yang berjudul "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.

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

Bagaimana Algoritma Kruskal Bekerja untuk Pembuatan Labirin

Langkah 1: Inisialisasi

• Perlakukan setiap sel dalam labirin sebagai himpunan terpisah (komponen unik).
• Sebutkan semua dinding antara sel yang bersebelahan sebagai sisi potensial.

Langkah 2: Urutkan Dinding

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

Langkah 3: Memproses Dinding

• Lakukan iterasi melalui dinding yang telah diacak.
• Jika kedua sel yang dipisahkan oleh dinding termasuk dalam himpunan yang berbeda (yaitu, belum terhubung dalam labirin), singkirkan dinding dan gabungkan himpunan tersebut.
• Jika mereka sudah berada dalam satu set yang sama, lewati dinding (untuk menghindari siklus).

Langkah 4: Lanjutkan Hingga Selesai

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

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

Bacaan Lebih Lanjut

Jika Anda menikmati postingan ini, Anda mungkin juga menyukai saran berikut:

• Generator Labirin Perburuan dan Bunuh
• Generator Labirin Algoritma Eller
• Generator Labirin Algoritma Pohon Tumbuh