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

Prima algoritmi 
Algoritm g`oyasi. Graf uchlarining ixtiyoriysi tanlanadi. So’ng ushbu uchdan 
chiqqan barcha qirralardan eng arzon qiymatlisi tanlanadi. Shunday qilib, ikkita 
uchli bitta qirrali daraxtni xosil qilamiz. Shundan so’ng bir uchi ushbu daraxtga 
tegishli bo`lgan barcha qirralardan eng arzon qiymatlisi tanlanadi. Bu qirra yoki 
qirralar, agar eng arzon qiymatlisi bir nechta bo`lsa, daraxtga qo`shiladi. Qirralarni 
qo`shish jarayoni bunday qo`shishlar sikl xosil qilinguncha davom etadi. Bunday 
daraxt qurish jarayoni asta-sekin grafni barcha uchlarini qamrab oladi. Shunday 
qilib, graf qirralaridan tashkil topgan daraxt xosil qilamiz, daraxtga qolgan 

---

uchlardan ixtiyoriysini qo`shilishi sikl xosil qiladi. Ostov daraxtini qurish jarayonini 
va yaqqol tasvirini avval keltirilgan misolda ko`ramiz. 
11.3rаsm 
B 
D 
5 
10 C 
7 
A 
8 
12 9 
6
15 
E 
G 
13 11 
8 
F 
Birinchi etapda biz ixtiyoriy uchini tanlab olamiz. Masalan, D uchini 
tanlaymiz. D uchidan ikkita DC va DE qirralar chiqib, ulardan eng arzon qiymatliysi 
DC qirra bo`ladi. Shunday qilib, bitta qirra DC va ikkita D va C uchdan tashkil 
topgan daraxt xosil qilamiz. 
Ushbu uchlardan DE, SB, SA, SE qirralar chiqadi. Ulardan qiymati bo`yicha 
eng arzoni SA qirra bo`ladi va uni qurilgan daraxtga qo`shib DSA daraxt xosil 
qilamiz 
11.4rаsm.
D 
7 
8 
C 
A 
Shundan so`ng, ushbu daraxt uchlaridan chiquvchi qirralardan eng arzon 
qiymatliysini tanlashimiz kerak. Bunday qirralar 6 ta bo`lib ular: DE, CB, CE, AB, 
AE, AG. Qiymati bo`yicha eng arzoni AB qirra bo`ladi. Uni qurilgan daraxtga 
qo`shib DSAV daraxt xosil qilamiz. 

---

11.5rаsm.
D 
B 7 
5 
8 
C 
A 
Xuddi shunday qoiida buyicha keyingi bosqichda AG qirra qo`shiladi va 
yana daraxt xosil qilinadi. 
11.6rаsm. 
D 
B 
7 
A 5 
8 
C 
6 
G 
Keyingi qadamda GF qirra qo`shiladi va 11.7 rasm ko`rinishidagi daraxt 
hosil bo`ladi 
11.7rаsm.
D 
B 
7 
A 5 
8 
C 
6 
G 
8 
F 
Shundаn so`ng ushbu dаrаxtgа qo`shish mumkin bo`lgаn qirrаlаrni qiymаti bo`yichа 
sаrаlаb DE qirrаni аniqlаymiz vа uni qo`shib 11.8 rаsm ko`rinishidаgi dаrаxtni hosil 
qilаmiz. 
11.8rаsm.
D 
B 
7 
9 
A 5 
8 
C E 
6 
G8 
F 
Agar bu daraxtni Kruskal algoritmi bo`yicha olingan daraxt bilan solishtirsak, 
ikkala xolda ham bir xil natijaga erishganimizni ko`ramiz. Ko`rinishidan sodda 
bo`lgan algoritmni batafsil tasvirlashimizga sabab shundaki, bu algoritmlarni 
dasturiy ifodalaganimizda vizual ifodada sezilmagan katta miqdordagi 

---

muammolarga duch kelamiz. Dasturiy ifoda jarayonida uchlari, qirralari va ularni 
insidentligi haqidagi barcha axborot kompyuter xotirasiga joyilangan bo`lishi kerak 
va dastur tuzish jarayoni ushbu axborotga asoslangan bo`lishi kerak. 

---