Kruskal sika Algorithm Maze Generator

I-algorithm ye-Kruskal iyi-algorithm encane yomuthi we-spanning engashintshwa isizukulwane se-maze. Kusebenza ikakhulukazi ekudaleni ama-mazes aphelele. Enye indlela ye-algorithm kaKruskal yi-algorithm ye-Prim, nayo i-algorithm encane yomuthi we-spanning, kodwa kusukela bakhiqiza ama-mazes afanayo kanye nokugijima kukaKruskal ngokushesha, angizange ngizihluphe ngokusebenzisa i-Prim's.

I-maze ephelele i-maze lapho kukhona indlela eyodwa ncamashi ukusuka kunoma iyiphi indawo ku-maze ukuya kunoma iyiphi enye indawo. Lokho kusho ukuthi ngeke ugcine usuzungeza emibuthanweni, kodwa uzohlangana nezinto ezifile, okuphoqa ukuthi ujike uphinde ubuyele emuva.

Amamephu we-maze akhiqizwe lapha afaka inguqulo ezenzakalelayo ngaphandle kwanoma yiziphi izindawo zokuqala nokuqeda, ukuze ukwazi ukuzinqumela lokho: kuzoba nesixazululo kusuka kunoma iyiphi indawo ku-maze kuya kunoma iyiphi enye indawo. Uma ufuna ugqozi, ungavumela indawo yokuqala neyokuqeda ephakanyisiwe - futhi ubone ngisho nesixazululo phakathi kwakho kokubili.

Mayelana ne-Algorithm kaKruskal

I-algorithm kaKruskal yadalwa nguJoseph Bernard Kruskal, Jr., isazi sezibalo saseMelika, isazi sezibalo, nososayensi wekhompyutha. Waqala ukuchaza i-algorithm ngo-1956 ephepheni lakhe elithi "On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem."

I-algorithm yenzelwe ukuthola umuthi omncane we-spanning (MST) wegrafu, ukuqinisekisa ukuthi wonke ama-vertices axhunywe ngesisindo esincane se-edge ephelele ngenkathi ugwema imijikelezo.

I-Algorithm ye-Kruskal isebenza kanjani ku-Maze Generation

Isinyathelo 1: Qalisa

• Phatha iseli ngalinye ku-maze njengesethi ehlukile (ingxenye eyingqayizivele).
• Hlela zonke izindonga phakathi kwamaseli aseduze njengemiphetho engaba khona.

Isinyathelo 2: Hlunga Izindonga

• Shuffle noma ngokungahleliwe oda izindonga. Uma ukuyisebenzisa njenge-algorithm yeqiniso ye-Kruskal, hlunga izindonga ngokulandelana okungahleliwe (kusukela isizukulwane se-maze asidingi izisindo).

Isinyathelo 3: Izindonga Zenqubo

• Iterate ngokusebenzisa izindonga shuffled.
• Uma amaseli amabili ahlukaniswe udonga kungokwalabo amasethi ezahlukene (okungukuthi, abakaxhunyiwe ku-maze), susa udonga bese uhlanganisa amasethi.
• Uma sebevele besesethi efanayo, yeqa udonga (ukugwema imijikelezo).

Isinyathelo 4: Qhubeka Kuze Kube Sekugcineni

• Phinda le nqubo kuze kube yilapho wonke amaseli exhunyiwe, akha umuthi owodwa othathayo.
• Ekugcineni, wonke amaseli axhunywe kwabanye ngaphandle kwama-loops noma izigaba ezihlukanisiwe.

Njengoba i-algorithm ye-Kruskal incike ekuhlanganiseni amasethi, ingalungiswa ngokusebenzisa i-algorithm ye-Union-Find, enikeza indlela ephumelelayo yokulandelela amaseli axhunyiwe ngesikhathi sesizukulwane se-maze. Ungabona ukuqaliswa kwami kwe-PHP ye-algorithm ye-Union-Find lapha: Isethi engahlangene (i-Union-Find Algorithm) ku-PHP