Алгоритмларни лойиҳалаш

Крускал Алгоритми
 
барча учларига эга бўлган 
граф остисини
хосил қиламиз. Ушбу граф остисида 
G 13 11 

---

3 
1
чи
босқич чизма АВни танлаш 
2
чи
босқиччизмаAГ ни қўшиш 
3
чи
босқиччизмаCDни қўшиш 
4
чи
босқиччизмаAC, GFларни қўшиш 
5
чи
босқиччизмаDEни қўшиш. 
Қолган қирралардан ихтиёрийсини берилган дарахтга қўшилиши 
цикллар хосил бўлишига олиб келади. Демак айнан шу дарахт қидирилаётган 
остов дарахти бўлади. Баёнимиз тўлиқ бўлиши учун дастлабки графни 
шундай тасвирлаймизки,остов дарахтининг қирралари текис -узлуксиз 
чизиқлар билан, қолган қирралар пунктир чизиқлар билан чизилган бўлади. 
11.2 расм.
D 
B 
A 
C 
E 
F 
Графнинг остов дарахтининг қўришнинг яна бир усулини кўрайлик. 
Прима алгоритми 
Алгоритм ғояси.Граф учларининг ихтиёрийси танланади. Сунг ушбу 
учдан чиқган барча қирралардан энг арзон қийматлийси танланади.Шундай 
қилиб иккита учли битта қиррали дарахтни хосил қиламиз. Шундан сунг бир 
учи ушбу дарахтга тегишли бўлган барча қирралардан энг арзон 
қийматлийси танланади. Бу қирра ёки қирралар,агар энг арзон қийматлийси 
бир нечта бўлса,дарахтга қўшилади.Қирраларни қўшиш жараёни бундай 
қўшишлар цикл хосил қилингунча давом этади. Бундай дарахт қуриш 
жараёни аста секин графни барча учларини қамраб олади. Шундай 
қилиб,граф қирраларидан ташкил топган дарахт хосил киламиз,дарахтга 
қолган учлардан ихтиёрийсини қўшилиши цикл хосил қилади. Остов 
дарахтини қуриш жараёнини ва яққол тасвирини аввал келтирилган мисолда 
кўрамиз. 

---

4 
11.3 расм
B 
D 
5 
10 C 
7 
A 
8 
12 9 
6
15 
E 
8 
F 
Биринчи этапда биз ихтиёрий учини танлаб оламиз. Масалан D учини 
танлаймиз. D учидан иккита DC ва DE қирралар чиқиб, улардан энг арзон 
қийматлийси DC қирра бўлади.Шундай қилиб битта қирра DC ва иккита D 
ва C учдан ташкил топган дарахт хосил қиламиз. 
Ушбу учлардан DЕ, СВ, СА, СЕ қирралар чиқади. Улардан қиймати бўйича 
энг арзони СА қирра бўлади ва уни қурилган дарахтга қўшиб ДСА дарахт 
хосил қиламиз 
11.4 расм.
D 
7 
8 
C 
A 
Шундан сўнг ушбу дарахт учларидан чиқувчи қирралардан энг арзон 
қийматлийсин танлашимиз керак. Бундай қирралар 6 бўлиб улар: DE, CB, 
CE, AB, AE, AG .Қиймати бўйича энг арзони АВ қирра бўлади. Уни қурилган 
дарахтга қўшиб ДСАВ дарахт хосил қиламиз. 
11.5 расм.
D 
B 7 
5 
8 
C 
A 
13 11 
G 

---

5 
Худди шундай қойида буйича кейнги босқичда AG қирра қўшилади ва яна 
дарахт хосил қилинади. 
11.6 расм. 
D 
B 
7 
A 5 
8 
C 
6 
G 
Кейинги қадамда GF қирра қўшилади ва 11.7 расм кўринишидаги дарахт 
хосил бўлади 
11.7 расм.
D 
B 
7 
A 5 
8 
C 
6 
G 
8 
F 
Шундан сўнг ушбу дарахтга қўшиш мумкин бўлган қирраларни қиймати 
бўйича саралаб DE қиррани аниқлаймиз ва уни қўшиб 11.8 расм 
кўринишидаги дарахтни хосил қиламиз. 
11.8 расм.
D 
B 
7 
9 
A 5 
8 
C E 
6 
G8 
F 

---

6 
Агар бу дарахтни Крускал алгоритми бўйича олинган дарахт билан 
солиштирсак , иккала холда хам бир хил натижага эришганимизни кўрамиз. 
Кўринишидан содда бўлган алгоритмни батафсил тасвирлашимизга сабаб 
шундаки, бу алгоритмларни дастурий ифодалаганимизда визуал ифодада 
сезилмаган катта миқдордаги муаммоларга дуч келамиз. Дастурий ифода 
жараёнида учлари, қирралари ва уларни инцидентлиги хақидаги барча 
ахборот ХМ хотирасига жойиланган бўлиши керак ва дастур тузиш жараёни 
ушбу ахборога асосланган бўлиши керак