Kruskal sika Algorithm Maze Generator

I-algorithm kaKruskal iyi-algorithm yesihlahla esibanzi esincane engashintshwa ukuze kukhiqizwe i-maze. Isebenza kahle kakhulu ekudaleni ama-maze aphelele. Enye indlela esikhundleni se-algorithm kaKruskal yi-algorithm kaPrim, nayo eyi-algorithm yesihlahla esibanzi esincane, kodwa njengoba ikhiqiza ama-maze afanayo futhi ukugijima kukaKruskal kushesha, angizange ngikhathazeke 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, kanye 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 iklanyelwe ukuthola umuthi omncane we-spanning (MST) wegrafu, ukuqinisekisa ukuthi wonke ama-vertice axhunywe nesisindo esincane kakhulu somphetho ophelele ngenkathi kugwenywa imijikelezo.

Indlela i-Algorithm kaKruskal Esebenza Ngayo Esizukulwaneni Se-Maze

Isinyathelo 1: Qalisa

• Phatha iseli ngalinye elise-maze njengesethi ehlukile (ingxenye eyingqayizivele).
• Bhala zonke izindonga eziphakathi kwamaseli aseduze njengezinqenqema ezingaba khona.

Isinyathelo 2: Hlela Izindonga

• Shaya noma uhlele izindonga ngokungahleliwe. Uma uyisebenzisa njenge-algorithm yangempela kaKruskal, hlunga izindonga ngokulandelana okungahleliwe (njengoba ukwenziwa kwe-maze kungadingi izisindo).

Isinyathelo 3: Izindonga Zenqubo

• Phindaphinda udlule ezindongeni ezihlanganisiwe.
• Uma amaseli amabili ahlukaniswe udonga engamalungu amasethi ahlukene (okungukuthi, awakaxhunywa ku-maze), susa udonga bese uhlanganisa amasethi.
• Uma sezivele zisesethini efanayo, yeqa udonga (ukuze ugweme imijikelezo).

Isinyathelo 4: Qhubeka Kuze Kuqedwe

• Phinda le nqubo kuze kube yilapho wonke amaseli exhunyiwe, kwakha umuthi owodwa obanzi.
• Ekugcineni, iseli ngalinye lixhunywe kwamanye ngaphandle kwezihibe noma izingxenye ezihlukanisiwe.

Njengoba i-algorithm kaKruskal incike ekuhlanganiseni amasethi, ingathuthukiswa ngokusebenzisa i-algorithm ye-Union-Find, enikeza indlela ephumelelayo yokulandelela amaseli axhunyiwe ngesikhathi sokukhiqizwa kwe-maze. Ungabona ukusetshenziswa kwami kwe-PHP kwe-algorithm ye-Union-Find lapha: Isixhumanisi

Ukufunda Okuqhubekayo

Uma ukujabulele lokhu okuthunyelwe, ungaphinda uthande lezi ziphakamiso:

• Recursive Backtracker Maze Generator
• Hunt futhi Kill Maze Generator
• Wilson sika Algorithm Maze Generator