“Ochko`z” Algoritmlar. Kruskal algoritmi. Prima algoritmi. Xoffman daraxti

 
Kruskal algoritmi 
Algoritm g`oyasini ifodalaylik. Avval daraxt qirralarining to`plami bo`sh 
deb e’lon qilinadi. Shundan so`ng mumkin bo`lgunga qadar keyingi amal bajariladi: 
barcha qirralardan, ularni mavjud to`plamga qo`shilishi sikl paydo bo`lishiga olib 
kelmaydigan qirralardan, eng arzon (eng kam xarajatli) qirrasi tanlab olinadi va 
mavjud to`plamga qo`shib qo`yiladi. Bunday qirralar qolmaganida, algoritm 
tugallanadi va biz dastlabki grafni barcha uchlariga ega bo`lgan grafostisini hosil 
qilamiz. Ushbu grafostisida sikllar bo`lmasligidan, u eng arzon (eng kam harajatli) 
daraxt bo`lib, uning boshqacha nomini ostov daraxti deb yuritiladi. Algoritmni 
yaqqol tasavvurini misolda amalga oshiramiz va barcha jarayonni bosqichma-
bosqich sxematik tarzda ifodalaymiz. Dastlabki graf 11.1.rasmda keltirilgan 
11.1.rasm 
B 
D 
5 
10 C 
7 
A 
8 
12 9 
6
15 
E 
G 
13 11 
8 
F 
Grafning har bir qirrasi ma’lum vaznga ega bo`lib, ostov daraxtini qurishda 
biz aynan qirralar vaznidan kelib chiqamiz. Buning uchun qirralarni vaznlari 
bo`yicha tartiblaymiz. Eng arzon 5 qiymatli qirra AB daraxt to`plamining birinchi 

---

elementi bo`ladi va keyngi AG, CD, AC, GF, DE qirralar qiymati bo`yicha daraxtga 
qo`shib boriladi 
1-bosqich chizma AB ni tanlash 
2-bosqich chizma AG ni qo`shish 
3-bosqich chizma CD ni qo`shish 
4-bosqich chizma AC, GF larniqo`shish 
5-bosqich chizma DE ni qo`shish. 
Qolgan qirralardan ixtiyoriysini berilgan daraxtga qo`shilishi sikllar xosil 
bo`lishiga olib keladi. Demak aynan shu daraxt qidirilayotgan ostov daraxti bo`ladi. 
Bayonimiz to`liq bo`lishi uchun dastlabki grafni shunday tasvirlaymizki, ostov 
daraxtining qirralari tekis-uzluksiz chiziqlar bilan, qolgan qirralar punktir chiziqlar 
bilan chizilgan bo`ladi. 
11.2 rasm. 
D 
B 
A 
C 
E 
F 
Grafning ostov daraxtini qurishning yana bir usulini ko`raylik.