"Алгоритмларни лойиҳалаш" фанидан маърузалар матни

Крускал Алгоритми
Алгоритм ғоясини ифодалайлик. Аввал дарахт қирраларининг тўплами бўш деб эълон қилинади. Шундан сўнг мумкин бўлгунга қадар кейинги амал бажарилади: барча қирралардан, уларни мавжуд тўпламга қўшилиши цикл пайдо бўлишига олиб келмайдиган қирралардан,энг арзон(энг кам харажатли) қирраси танлаб олинади ва мавжуд тўпламга қўшиб қўйилади. Бундай қирралар қолмаганида,алгоритм тугалланади ва биз дастлабки графни барча учларига эга бўлган графостисини хосил қиламиз. Ушбу графостисида циклар бўлмаслигидан,у энг арзон(энг кам харажатли)дарахт бўлиб,унинг бошқача номиниостов дарахти деб юритилади. Алгоритмни яққолтасаввурини мисолда амалга оширамиз ва барча жараённи босқичма-босқич схематик тарзда ифодалаймиз. Дастлабки граф 11.1.расмда келтирилган
11.1.расм
B D
5 10 C 7
A 8 12 9
6 15 E
G 13 11
8 F

Графнинг хар бир қирраси маълум вазнга эга бўлиб, остов дарахтини қуришда биз айнан қирралар вазнидан келиб чиқамиз. Бунинг учун қирраларни вазнлари бўйича тартиблаймиз. Энг арзон 5 қийматли қирра АВ дарахт тўпламининг биринчи элементи бўлади ва кейнги AG, CD, AC, GF, DE қирралар қиймати бўйича дарахтга қўшиб борилади

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

E
F
Графнинг остов дарахтининг қўришнинг яна бир усулини кўрайлик.