Kruskal urang Algoritma Maze generator

Algoritma Kruskal nyaéta algoritma tangkal rentang minimum anu tiasa diadaptasi pikeun generasi labirin. Ieu hususna efektif pikeun nyiptakeun labirin anu sampurna. Alternatif pikeun algoritma Kruskal nyaéta algoritma Prim, anu ogé mangrupikeun algoritma tangkal rentang minimum, tapi kumargi aranjeunna ngahasilkeun labirin anu idéntik sareng Kruskal ngajalankeun langkung gancang, kuring henteu repot-repot nerapkeun Prim.

Maze sampurna nyaéta Maze dimana aya persis hiji jalur ti titik mana waé dina Maze ka titik séjén. Éta hartina anjeun moal bisa mungkas nepi ka sabudeureun dina bunderan, tapi anjeun bakal mindeng sapatemon dead ends, forcing anjeun ngahurungkeun sabudeureun tur balik.

Peta Maze anu dihasilkeun di dieu kalebet versi standar tanpa posisi awal sareng akhir, ku kituna anjeun tiasa mutuskeun pikeun diri anjeun: bakal aya solusi ti mana waé dina maze ka titik anu sanés. Upami anjeun hoyong inspirasi, anjeun tiasa ngaktipkeun posisi mimiti sareng bérés anu disarankeun - komo ningali solusi antara dua.

Ngeunaan Algoritma Kruskal

Algoritma Kruskal diciptakeun ku Joseph Bernard Kruskal, Jr., saurang ahli matematika, statistikawan, sareng élmuwan komputer Amérika. Anjeunna mimiti ngajelaskeun algoritma ieu dina taun 1956 dina makalahna "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem.

Algoritma ieu dirancang pikeun milarian tangkal rentang minimum (MST) tina hiji grafik, mastikeun yén sadaya simpul nyambung kalayan beurat sisi total minimal anu mungkin bari nyingkahan siklus.

Kumaha Algoritma Kruskal Gawéna pikeun Generasi Labirin

Léngkah 1: Inisialisasi

• Anggap unggal sél dina labirin salaku sét anu misah (komponén anu unik).
• Sebutkeun sadaya témbok antara sél anu padeukeut salaku sisi poténsial.

Léngkah 2: Susun Tembok

• Kocok atawa urutkeun témbok-témbokna sacara acak. Upami nerapkeunana salaku algoritma Kruskal anu saleresna, urutkeun témbok sacara acak (sabab nyieun labirin teu merlukeun beurat).

Léngkah 3: Témbok Prosés

• Ngaliwatan témbok-témbok anu dikocok deui.
• Upami dua sél anu dibagi ku témbok kagolong kana sét anu béda (contona, éta sél tacan nyambung dina labirin), cabut témbokna teras gabungkeun sét-sét éta.
• Upami aranjeunna parantos aya dina set anu sami, lewati témbok (pikeun nyingkahan siklus).

Léngkah 4: Teraskeun Nepi ka Réngsé

• Balikan deui prosés ieu dugi ka sadaya sél nyambung, ngabentuk hiji tangkal rentang tunggal.
• Pamustunganana, unggal sél disambungkeun ka sél séjénna tanpa puteran atawa bagian anu misah.

Kusabab algoritma Kruskal ngandelkeun ngahijikeun set, éta tiasa dioptimalkeun ku ngagunakeun algoritma Union-Find, anu nyayogikeun cara anu efisien pikeun ngalacak sél anu nyambung nalika generasi labirin. Anjeun tiasa ningali implementasi PHP kuring ngeunaan algoritma Union-Find di dieu: Tautan

Bacaan salajengna

Upami anjeun resep kana tulisan ieu, anjeun ogé tiasa resep saran ieu:

• Generator Labirin Algoritma Eller
• Algoritma Maze generator Wilson urang
• Tumuwuh Tangkal Algoritma Maze Generator