Generator labirin Algoritma Kruskal

Algoritma Kruskal minangka algoritma wit spanning minimal sing bisa diadaptasi kanggo nggawe maze. Utamane efektif kanggo nggawe labirin sing sampurna. Alternatif kanggo algoritma Kruskal iku algoritma Prim, kang uga algoritma wit spanning minimal, nanging wiwit padha generate mazes podho rupo lan Kruskal mlaku luwih cepet, Aku wis ora keganggu ngleksanakake Prim.

Labirin sing sampurna yaiku labirin sing ana persis siji dalan saka sembarang titik ing mbingungake menyang titik liyane. Iku tegese sampeyan ora bisa mungkasi munggah ing bunderan, nanging sampeyan bakal kerep nemoni bund ends, meksa sampeyan kanggo nguripake lan bali.

Peta mbingungake sing digawe ing kene kalebu versi standar tanpa posisi wiwitan lan pungkasan, supaya sampeyan bisa mutusake dhewe: bakal ana solusi saka sembarang titik ing mbingungake menyang titik liyane. Yen sampeyan pengin inspirasi, sampeyan bisa ngaktifake posisi wiwitan lan pungkasan sing disaranake - lan malah ndeleng solusi ing antarane loro kasebut.

Babagan Algoritma Kruskal

Algoritma Kruskal digawe dening Joseph Bernard Kruskal, Jr., ahli matematika, ahli statistik, lan ilmuwan komputer Amerika. Dheweke pisanan nggambarake algoritma kasebut ing taun 1956 ing makalah "On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem."

Algoritma iki dirancang kanggo nemokake wit spanning minimal (MST) saka grafik, kanggo mesthekake yen kabeh verteks disambungake karo bobot pinggiran paling tithik nalika ngindhari siklus.

Cara Kerja Algoritma Kruskal kanggo Generasi Maze

Langkah 1: Initialize

• Nambani saben sel ing mbingungake minangka set kapisah (komponen unik).
• Dhaptar kabeh tembok antarane sel jejer minangka sudhut potensial.

Langkah 2: Urut Tembok

• Acak utawa kanthi acak supaya tembok. Yen ngleksanakake minangka algoritma Kruskal sing bener, ngurutake tembok kanthi urutan acak (amarga generasi mbingungake ora mbutuhake bobot).

Langkah 3: Tembok Proses

• Ngulang liwat tembok sing dikocok.
• Yen rong sèl sing dipérang dadi tembok dadi klompok sing béda (yaiku, durung disambungake ing mbingungake), copot tembok lan gabungke set kasebut.
• Yen padha wis ing pesawat padha, skip tembok (kanggo supaya siklus).

Langkah 4: Terusake Nganti Rampung

• Baleni proses iki nganti kabeh sel disambungake, mbentuk wit spanning siji.
• Ing pungkasan, saben sel disambungake menyang liyane tanpa puteran utawa bagean sing terisolasi.

Wiwit algoritma Kruskal gumantung ing nggabungake set, bisa dioptimalake kanthi nggunakake algoritma Union-Find, sing nyedhiyakake cara sing efisien kanggo nglacak sel sing disambungake sajrone nggawe mbingungake. Sampeyan bisa ndeleng implementasine PHP saka algoritma Union-Find ing kene: Disjoint Set (Union-Find Algorithm) ing PHP