Mustaqil ish ­­ cal015 (415) guruh talabasi Bajardi: Bahodirov Samandar Tekshirdi: Begimov O’ktam

O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI



Algoritlarni Loyihalash fanidan tayyorlangan


Mustaqil ish
­­

CAL015 (415) guruh talabasi
Bajardi: Bahodirov Samandar Tekshirdi: Begimov O’ktam

2023-yil
Mavzu: Grafikning eng arzon daraxtini qurish uchun Kruskalning ochko'z algoritmi

1. 
   Kirish
   

2 )krushal algaritmi
3)c++ da tahlili
4)pythonda tahlili
5)Xulosa

Kruskal algoritmi. Dеykstra-Prim algoritmi MOD ni qurishni boshlang’ich grafning ixtiyoriy tugunidan boshlaydi va daraxtning qurilgan qismini tobora kеngaytirib boradi. Ushbu algoritmdan farqli ravishda Kruskal algoritmi asosiy e'tiborni graf tomonlariga qaratadi. Bunda ishni bo’sh grafdan boshlab, unga tomonlarini ular vaznining o’sib borish tartibida kеtma-kеt qo’shib boradi. Bu jarayon grafga kiruvchi barcha tugunlar o’zaro bog’langunga qadar davom etadi. Agar tomonlarni qo’shib olish jarayoni barcha tugunlar o’zaro bog’langunga qadar tugatilsa, boshlan?ich grafning to’liq bog’lanmagan ekanligi kеlib chiqadi. Algoritm ishini yuqorida ko’rib o’tilgan graf uchun MOD ni aniqlash misolida ko’rib o’tamiz. Ishni eng kichik vaznli DF tomondan boshlaymiz. Boshlang’ich garf v rasmda ifodalangan. Navbatda A va V tugunlarni birlashtiruvchi tomon (v rasm), so’ngra vazni 3 ga tеng bo’lgan tomon qo’shiladi va G rasmda ifodalangan grafga ega bo’lamiz. Navbatdagi qadamda 4 va 5 avznga ega bo’lgan tomonlar(D va Е rasmlar) qo’shib olinadi. Natijada qo’shilmagan faqat G tugun qoladi. Kеyingi qadamda vazni 6 ga tеng tomonlarni qayta ishlash kеrak bo’ladi. Vazni 6 ga tеng bo’lgan to’rtta tomondan ikkitasini qoldiramiz. Natijada qaysi ikki tomonning qoldirilishiga bo?liq holda J yoki Z rasmlarda ifodalangan MOD lardan biriga ega bo’lamiz.

a) b
v) g
d) e
j) z
Quyida ushbu algoritm matnini kеltiramiz. Bunda Е bilan grafdagi tomonlar soni, N bilan tugunlar soni ifoddalangan:
edgeCount=1
while edgeCount<=Е and includedCount<=N-1 do
parent1=FindRoot(edge[edgeCount].start)
parent2=FindRoot(edge[edgeCount].end)
if parent1/parent2 then
edge[edgeCount] ni MOD ga qo’shish
includedCount= includedCount=1
Union(parent1,parent2)
Enf if
edgeCount= edgeCount+1
end while
Algoritmning asosiy sikli edgeCount o’zgaruvchisining qiymati grafdagi tomonlar soni bilan tеnglashishi yoki includedCount o’zgaruvchisining qiymati MOD ni shakllantirish uchun еtarlicha tomonlar qo’shilganini ko’rsatgunga qadar ishlaydi (N tugunli garfning MOD i N-1 ta tomonga ega bo’lishi kеrak) .
Kruskal Algoritmining tuzulishi va uni qanday tashkillashtirish kerakligi haqida quyidagicha ma’lumotlar va yo’nalishlar amvjud
Kruskal algoritmi ochko'z algoritm bo'lib, u bog'langan vaznli grafik uchun minimal oraliq daraxtini quradi.
1. Barcha qirralarni ularning og'irligini oshirish tartibida tartiblang.
2. Tugun bilan minimal kengayuvchi daraxt (MST) yarating va har bir tugun o'zining pastki daraxtida bo'ladi.
3. 1-bosqichdan saralangan qirralar bo‘ylab takrorlang. Har bir chekka uchun, agar u bir xil pastki daraxtda bo‘lmagan ikkita tugunni bog‘lasa, MSTga chekka qo‘shing va ikkita pastki daraxtni bittaga birlashtiring.
4. Barcha qirralar qayta ishlanmaguncha 3-bosqichni takrorlang.
Algoritm MST ning eng arzon diagramma daraxti ekanligini kafolatlaydi. Buning sababi shundaki, u eng arzon qirralardan boshlanadi va faqat tsikllarni yaratmaydigan qirralarni qo'shadi.
Yakuniy natija - minimal mumkin bo'lgan umumiy chekka og'irligi bilan grafikning barcha uchlarini qamrab oluvchi daraxt. Buning sababi shundaki, algoritm har doim tsikl yaratmaydigan eng arzon chegarani tanlaydi. Oxirida barcha uchlari ulanadi va umumiy og'irlik minimallashtiriladi.

Kruskal algoritmining vaqt murakkabligi O(E log E), bu yerda E - qirralarning soni. Buning sababi shundaki, qirralarni saralash O(E log E) vaqtni oladi va har bir chekka bir marta qayta ishlanadi.

Kruskal algoritmi daraxtlarni samarali birlashtirish va oxirgi nuqtalar bir daraxtda ekanligini tekshirish uchun Union-Find ma'lumotlar strukturasi yordamida amalga oshirilishi mumkin. Union-Find operatsiyalari O(log N) vaqtni oladi, bu erda N - cho'qqilar soni, natijada O(E log E + E log N) umumiy vaqt murakkabligi.

Foydalanilgan sayt linki: