Telekommunikatsiya va kommunikatsiyalarni rivolantirish vazirligi

 
V
(D,B) = 9 
(D,E)= 
15 
(D,F) = 6 
{A,B,C,E,
F,G} 
D
tugundan 
boshlaymiz 
A
, 
B
, 
E
i 
F
lar 
D
bilan 
boqlangan. 
A
tugun 
— 
D
ga eng yaqin 
bo’lganligi uchun shu 
tugun olinadi. 
Ushbu muammoni hal qilishda foydalanadigan algoritmga Primning algoritmi 
deyiladi. Bu "Xasis
algoritmlar" deb nomlangan oilaga tegishli, chunki har bir qadamda 
tavsiya etilgan yo'llarning eng arzoni tanlanadi. Bunday holda, bu eng kam og'irlik bilan 
chekka bo'ylab harakatlanish bo'ladi. Bizning yakuniy vazifamiz Primning algoritmini 
amalga oshirishdir. 
Daraxt yaratish uchun asosiy g'oya quyidagicha: 
Toki T - taralayotgan daraxt 
Daraxtga xavfsiz tarzda qo'shilishi mumkin bo'lgan chekkani toping 
T ga yangi chekka qo'shing 
Qo'lga olish "xavfsiz tarzda qo'shish uchun chekka toping". Xavfsiz chekkani 
vertikalni uzaygan daraxtdan uning tashqarisidagi tepalikka bog'laydigan chekka deb 

---

belgilaymiz. Bu daraxt har doim daraxt bo'lib qolishini va tsikllarga ega bo'lmasligini 
ta'minlaydi. 
Prima
algoritmini amalga oshirish uchun Python kodi Listing 2 da ko'rsatilgan. 
Dijkstra algoritmiga o'xshaydi, chunki ular ikkalasi ham o'sib boruvchi grafaga 
qo'shilish uchun navbatdagi tepalikni tanlash uchun ustuvor navbatdan foydalanadilar.
N 
ta ahоli yashaydigan nuqtalar berilgan bo’lib, ularning har bir jufti o’rtasidagi 
masоfa ma`lum bo’lsin. Bu nuqtalarni shunday birlashtirish talab qilinadiki, har bir 
nuqtadan bоshqasiga yo’l mavjud bo’lsin hamda umumiy masоfa eng kichik bo’lsin.
Agar nuqtalarni grafning uchlari, ular o’rtasidagi masоfalarni qirra uzunliklari 
deb qaralsa, qo’yilgan masala minimal sinchli daraxt masalasiga aylanadi.