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
Do'stlaringiz bilan baham: |