Miklix
Kaca Ngarep / Labirin / Generator Labirin / Generator labirin Algoritma Kruskal

Generator labirin Algoritma Kruskal

Diterbitake: 16 Februari 2025 ing 18:03:47 UTC
Dianyari pungkasan: 12 Januari 2026 ing 08:59:33 UTC

Generator labirin nggunakake algoritma Kruskal kanggo nggawe labirin sing sampurna. Algoritma iki cenderung nggawe labirin kanthi koridor dawane sedheng lan akeh dalan buntu, uga solusi sing cukup lurus.

Kaca iki diterjemahake mesin saka basa Inggris supaya bisa diakses dening akeh wong. Sayange, terjemahan mesin durung dadi teknologi sing sampurna, mula kesalahan bisa kedadeyan. Yen sampeyan seneng, sampeyan bisa ndeleng versi Inggris asli ing kene:

Kruskal's Algorithm Maze Generator

Algoritma Kruskal kuwi algoritma wit rentangan minimum sing bisa diadaptasi kanggo generasi labirin. Iki efektif banget kanggo nggawe labirin sing sampurna. Alternatif kanggo algoritma Kruskal yaiku algoritma Prim, sing uga minangka algoritma wit rentangan minimum, nanging amarga padha ngasilake labirin sing identik lan Kruskal mlaku luwih cepet, aku ora repot-repot ngetrapake 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.


Nggawe labirin anyar








Babagan Algoritma Kruskal

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

Algoritma iki dirancang kanggo nemokake wit rentang minimum (MST) saka grafik, kanggo njamin yen kabeh simpul kasambung karo bobot pinggiran total minimal sing bisa ditindakake nalika ngindhari siklus.

Cara Kerja Algoritma Kruskal kanggo Generasi Labirin

Langkah 1: Inisialisasi

  • Anggep saben sel ing labirin minangka himpunan sing kapisah (komponen sing unik).
  • Dhaptar kabeh tembok antarane sel sing jejer minangka pinggiran potensial.

Langkah 2: Ngurutake Tembok

  • Kocok utawa urutna tembok kanthi acak. Yen ngetrapake minangka algoritma Kruskal sing sejati, urutna tembok kanthi urutan acak (amarga nggawe labirin ora mbutuhake bobot).

Langkah 3: Tembok Proses

  • Mlaku-mlaku liwat tembok sing dikocok.
  • Yen rong sel sing dipérang déning tembok kalebu himpunan sing béda (yaiku, durung kasambung ing labirin), copot tembok kasebut lan gabungaké himpunan kasebut.
  • Yen wis ana ing set sing padha, lewati tembok (kanggo nyegah siklus).

Langkah 4: Terusake Nganti Rampung

  • Baleni proses iki nganti kabeh sel nyambung, mbentuk wit rentang tunggal.
  • Ing pungkasan, saben sel disambungake karo liyane tanpa puteran utawa bagean sing kapisah.

Amarga algoritma Kruskal gumantung marang penggabungan set, mula bisa dioptimalake kanthi nggunakake algoritma Union-Find, sing nyedhiyakake cara sing efisien kanggo nglacak sel sing terhubung sajrone generasi labirin. Sampeyan bisa ndeleng implementasi PHP saka algoritma Union-Find ing kene: Link

Wacan Salajengipun

Yen sampeyan seneng karo kiriman iki, sampeyan bisa uga seneng saran iki:


Nuduhake ing BlueskyNuduhake ing FacebookNuduhake ing LinkedInNuduhake ing TumblrNuduhake ing XNuduhake ing LinkedInPin ing Pinterest

Mikkel Christensen

Babagan Penulis

Mikkel Christensen
Mikkel minangka pencipta lan pemilik miklix.com. Dheweke duwe pengalaman luwih saka 20 taun minangka programmer komputer / pangembang piranti lunak profesional lan saiki kerja full-time kanggo perusahaan IT Eropa sing gedhe. Nalika ora ngeblog, dheweke mbuwang wektu luang kanggo macem-macem minat, hobi, lan kegiatan, sing bisa uga katon ing macem-macem topik sing dibahas ing situs web iki.