Telekommunikatsiya va kommunikatsiyalarni rivolantirish vazirligi



Download 345,2 Kb.
Pdf ko'rish
bet3/7
Sana03.05.2023
Hajmi345,2 Kb.
#934439
1   2   3   4   5   6   7
Bog'liq
Yeshbayev Muxtar

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, 

(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

Download 345,2 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish