Telekommunikatsiya va kommunikatsiyalarni rivolantirish vazirligi

O (M log N + N
2
)
vaqtda bajariladi. Qirralarni saralash uchun 
O(M logN) ta operasiya kerak buladi. Tugun u yoki bu qism daraxtga tegishli bo’lsa, 
tree_id massiv yordamida saqlanadi, bu massivda har bir tugun uchun u tegishli 
bo’lgan daraxt nomeri saqlanadi. Har bir qirra uchun O(1) vaqtda uning tugunlari turli 
daraxtlarga tegishli ekanligini aniqlanadi. Nihoyat, ikkita daraxtni birlashtirish O (N) 
vaqtda bajariladi. Birlashtirish operatori O(N) o’tishda bajarilishini hisobga olsak, 
O 
(M log N + N
2
)
kelib chikadi. 
Prima algoritmi 
 
Algoritmni 1930 yilda chex matematikasi Voytex Jarnik yaratgan va keyinchalik 
1957 yilda kompyuter olimlari Robert C. Prim va 1959 yilda Edsger V.Daykstra 
tomonidan qayta kashf etilib, qayta nashr etilgan. Shuning uchun uni ba'zida Jarnik 
algoritmi, Prim – Jarnik algoritmi, Prim –Daykstra algoritmi yoki DJP algoritmi deb 
ham atashadi. 

---

Algoritmning birinchi muallifi Voytex Jarnik 1897-yil 22-dekabrda Paragada 
tug’ilgan. 1921 yilda u tabiiy fanlar bo'yicha doktorlik dissertatsiyasini oldi. 1919-1921 
yillarda u Brno texnika universitetida assistent bo'lib ishlagan. 1921 yildan - Pragadagi 
Charlz universitetida o'qituvchi. 1929-1967 yillarda - Praga universitetining matematika 
professori. 1930-yilda shu algoritmni yaratgan. 
Algoritmning o'zi juda oddiy. Kerakli minimal skelet asta-sekin qirralarni birma-
bir qo'shib quriladi. Dastlab skelet bitta tepadan iborat deb taxmin qilinadi (u 
o'zboshimchalik bilan tanlanishi mumkin). Keyin ushbu tepalikdan kelib chiqadigan 
minimal og'irlikdagi chekka tanlanadi va minimal skeletga qo'shiladi. Shundan so'ng, 
skelet allaqachon ikkita tepalikni o'z ichiga olgan va hozirda eng kam og'irlikdagi 
chekka qidiriladi va qo'shiladi, uning bir uchi tanlangan ikkita tepaning birida, 
ikkinchisida, aksincha, boshqa uchlari bor, bundan mustasno bu ikkitasi. Va shunga 
o'xshash narsalar, ya'ni har safar minimal og'irlik qirrasi izlanadi, uning bir uchi 
allaqachon skeletga kiritilgan tepalik bo'lib, boshqa uchi hali olinmagan va bu chekka 
skeletga qo'shilgan (agar shunday qirralar bir nechta bo'lsa, siz har qanday narsani 
oling). Bu jarayon skelet barcha tepaliklarni (yoki bir xil bo'lgan n -1 qirralarni) o'z 
ichiga olguncha takrorlanadi. Natijada minimal skelet quriladi. Agar grafik dastlab 
ulanmagan bo'lsa, unda skelet topilmaydi (tanlangan qirralarning soni n -1 dan kam 
bo'lib qoladi). 
Daraxtning minimal qiymatini topish uchun Primning algoritmi (Kruskal algoritmi 
kabi) ochko'zlik usulidan foydalanadi. Primning algoritmi eng qisqa yo'l birinchi 
algoritmlari bilan o'xshashlikni taqsimlaydi. 
Prima algoritmi, Kruskal algoritmidan farqli o'laroq, tugunlarni bitta daraxt sifatida 
ko'rib chiqadi va berilgan grafikadan yangi daraxt tugunlarini qo'shishda davom etadi. 
Kruskal algoritmidan farqli o'laroq va Primning algoritmini yaxshiroq tushunish 
uchun biz o'sha misoldan foydalanamiz 
Minimal narxli daraxtlar skletini qurishning 
ikkita keng tarqalgan usuli mavjud. Ulardan biri Prim algoritmi. Bu algoritmda daraxtlar 
skleti «o’sadigan» ("vыrastayet") U qirralar to’plami quriladi. V={1, 2,..., n} bo’lsin. 
Avval U={1} bo’ladi. Algoritmning har bir qadamida minimal narxli qirra topiladi, 

---

undan keyin v qirra V\U to’plamdan U to’plamga o’tkaziladi. Bu jarayon U to’plam V 
to’plamga teng bo’lguncha takrorlanadi.
{ } 
{A,B,C,D,
E,F,G} 
Boshlang’ich graf 
{D} 
(D,A)=5