175
3)
Boruvka algoritmi,
4)
Orqadan o'chirish algoritmi
Quyida ushbu algoritmlarni koʻrib chiqamiz.
59-rasm. Eng kichik uzunlikka ega boʻlgan daraxt
15.1. Kruskal algoritmi
Kruskal algoritmida qirralarning butun birlashtirilgan ro'yxati
kamaymaydigan uch darajalariga muvofiq tartiblangan.
Bundan tashqari,
qirralar darajalari kichikroq bo'lgan qirralardan yuqori tomonga siljiydi
va keyingi uch ilgari tanlangan qirralar bilan sikl hosil qilmasa, karkasga
qo'shiladi. Xususan, grafdagi minimal darajadagi qirralaridan biri har
doim birinchi bo'lib tanlanadi.
Tanlangan qirralarning sikl hosil qilmasligini tekshirish uchun biz
grafni bir nechta bogʻlangan komponentlarning
birlashishi sifatida
namoyish etamiz. Eng boshida, grafning chekkalari tanlanmaganida, har
bir uch alohida bogʻlangan komponent hisoblanadi. Yangi qirralar
qo'shilganda, ulanish komponentlari bitta umumiy ulanish komponenti
bo'lguncha
birlashadi.
Barcha
bogʻlangan
tarkibiy
qismlarni
raqamlaymiz va har bir uch uchun uning
ulangan qismlarini sonini
saqlaymiz, shuning uchun har bir uch uchun boshida uning bogʻlangan
komponentlari soni uchning o'zi soniga teng bo'ladi va oxirgi barcha
176
uchlar bir-biriga bogʻlangan komponentning bir xil raqamlariga tegishli
bo'ladi.
Keyingi qirrani ko'rib chiqayotganda,
ushbu qirraning uchlariga
to'gʻri keladigan ulangan komponentlarning raqamlarini ko'rib chiqamiz.
Agar bu raqamlar bir xil bo'lsa, unda qirra allaqachon bir xil bogʻlangan
komponentda joylashgan ikkita uchni birlashtiradi, shuning uchun bu
qirrani qo'shish siklni tashkil qiladi. Agar qirra ikki xil bogʻlangan
komponentni, masalan,
va
raqamlari bilan bogʻlasa,
u holda qirra
asosiy daraxtning bir qismiga qo'shiladi va bu ikkita bogʻlangan
komponentlar birlashtiriladi. Buning uchun, masalan, ilgari
komponentida bo'lgan barcha uchlar
uchun komponent raqamini
ga
o'zgartirish kerak.
Kruskal algoritmini amalga oshirish bosqichlari quyidagicha:
1) Barcha qirralarni quyidan yuqorigacha saralash.
2) Vazni eng kichik qirrasini oling va uni daraxtga qo'shing. Agar qirra
qoʻshilganda, sikl hosil boʻlsa, u holda bu qirrani olib tashlang.
3) Barcha uchlarga yetguncha qirralarni qo'shishni davom eting.
Quyidagi rasmda minimal uzunlikka kiritilgan qirralar qizil rang
bilan, qora rang bilan esa nomzodlar ulardan eng kam darajadagi qirra
tanlangan.
1-qadam
2-qadam
