“Ma’lumotlar tuzilmasi va algoritmlar” fanining maqsadi va vazifasi

Primo algoritmi samaradorligi

• Samaradorlik grafni tashkil etish va minimal narxli daraxtga tegishli bo’lmagan tugunlarni saqlash usuliga bog’liq.
• Agar Q navbat massiv ko’rinishida tashkil etilsa, Extract.Min(Q) amali O(n) ga bog’liq va minimal vaznli yoylarni daraxtga o’zlashtirishga O(1) ta amal sarflanadi.
• Agar Q navbat binar piramida ko’rinishida tashkil etilsa, u xolda Extract.Min(Q) amali O(log(n)) gacha kamayadi.ammo minimal vaznli yoylarni daraxtga o’zlashtirish amali miqdori O(log(n)) ga oshadi.

Kruskal algoritmi

• Algoritm dastlab 1956 yilda Jozef Kruskal tomonidan taklif etilgan.
• Dastlab yoylarning boshlang’ich to’plami bo’sh deb olinadi.
• Keyin, imkoni bo’sa, quyidagi amal bajariladi:
• Mavjud yoylar qarab chiqiladi, ularni daraxtga qo’shganda xalqa xosil bo’lmaydigan bo’lsa, ularning vazni minimali olinadi va daraxtga qo’shiladi.
• Agar bunday yoylar bo’lmasa, algoritm tugallanadi.
• Graf tugunlaridan xosil bo’lgan qismgraf minimal narxli daraxt xisoblanadi.

Algoritmga misol

tasvir	izox
	AD va CE yoylar minimal vaznga ega - 5. ixtiyoriy bittasi tanlanadi., masalan AD
	Keyingi kichikroq yoy 5 - CE. Yoyi xisoblanadi. Uni tanlanganda xalqa xosil bo’lmaydi.
	Vazni 6 ga teng bo’lgan DF yoyi tanlanadi.

Algoritmga misol

tasvir	izox
	AB va BE yoylar vazni 7. AB ni ixtiyoriy tanlaymiz, BD yoy tanlanmaydi, chunki ABD xalqa xosil bo’lishi mumkin.
	Vazni 7 bo’lgan BE yoy tanlanadi. BC yoy olinmaydi, chunki BCE xalqa, DE xam olinmaydi, chunki DEBA xalqa, FE xam olinmaydi, chunki FEBAD xalqa.
	Vazni 9 bo’o’lgan EG yoy qo’shiladi va algoritm tugullanadi. Minimal narxli daraxt aniqlandi.