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

Chiqish

Ushbu chiqishning to'g'riligini yuqorida ko'rsatilgan MST tuzilishi bilan solishtirish orqali tekshirishingiz mumkin. Ushbu MST uchun umumiy xarajat 5 ni tashkil qiladi.

Kruskal va Prim algoritmi

Kruskal algoritmi

Kruskalning ochko'z algoritmi vaznli, yo'naltirilmagan grafik uchun minimal oraliq daraxtini topadi. Algoritm grafikning alohida tugunlaridan tashkil topgan o'rmondan boshlanadi va keyin har bir tugundan eng arzon chetini topadi va uni o'rmonga qo'shadi. Bu jarayon o'rmonda faqat bitta daraxt bo'lgunga qadar takrorlanadi, minimal kenglikdagi daraxt.
Kruskal algoritmi - bu grafikni kirish sifatida qabul qiluvchi va ushbu grafik qirralarining pastki to'plamini topadigan minimal kengaytmali daraxt algoritmi. Ushbu kiritish har bir cho'qqini o'z ichiga olgan daraxtni hosil qiladi, bu erda daraxtdagi barcha qirralarning umumiy og'irligi minimallashtiriladi. Algoritm grafik qirralarini og‘irlik bo‘yicha saralash, so‘ngra grafikdan eng kichik og‘irlikdagi chetini olib, daraxtga qo‘shish orqali ishlaydi. Bu jarayon barcha uchlari daraxtga kiritilguncha takrorlanadi.

Prim algoritmi

Prim algoritmi ham ochko'z va og'irligi yo'naltirilmagan grafik uchun minimal oraliq daraxtini topadi. Shu bilan birga, algoritm bitta tugun bilan boshlanadi va keyin bu tugunning eng arzon chetini daraxtga qo'shadi. Lekin Prim algoritmi Kruskal algoritmidan boshqacha ishlaydi. Va bu jarayon daraxtda n-1 qirralar paydo bo'lguncha takrorlanadi, bu erda n - grafikdagi tugunlar soni.

Kruskal algoritmining murakkabligi

Kruskal algoritmi grafikning minimal chegaralangan daraxtini topishning mashhur algoritmidir. Bu ochko'z algoritm bo'lib, minimal kenglikdagi daraxtning chekkalari boshqa har qanday kenglikdagi daraxtning qirralarini tashkil etishi kerakligidan foydalanadi.
Kruskal algoritmining vaqt murakkabligi O(ElogE) ga teng, bu erda E - grafikdagi qirralarning soni. Bu murakkablik, chunki algoritm O(logE) vaqt murakkabligi bilan ustuvor navbatdan foydalanadi. Biroq, algoritmning fazoviy murakkabligi O(E) dir, bu nisbatan yuqori.