|
Muhammad al- xorazmiy nomidagi toshkent axborot texnalogiyalri unversiteti
|
| bet | 1/7 | | Sana | 28.07.2023 | | Hajmi | 0.93 Mb. | | #77545 |
Bog'liq algoritm mustaqil ish иш хақи, Mavzu Antivirus-dasturlari, 1-SINF, V sinf texnologiya va dizayn yo‘nalishi buyicha 5-sinflar uchun , Nometal materiallar, Жуфт сузлар, дарс ишланма сон, BEKLEMISHEV KLASSIFIKATSIYASIGA KO, A new generation of realistic writers, Ochiq faoliyat ishlanma 2, Zamonaviy sun, 1-oktyabr oqituvchi va murabbiylar www.sadikov.uz (1)Bu sahifa navigatsiya:
- Mavzu
O’ZBEKISTON RESPUBLIKASI AXBOROT KOMMUNIKATSIYA VA TEXNALOGIYALARINI RIVOJLANTIRISH VAZIRLIGI
MUHAMMAD AL- XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNALOGIYALRI UNVERSITETI
Алгоритм лойиҳалаш
MUSTAQIL ISH
Mavzu: Graflarni eng arzon tayanch daraxtini qurishda Kruskal xasis algoritmi.
Topshirdi: Yo`ldoshev Sh
Guruh: 713-21
Toshkent – 2023
Reja :
1) Minimal daraxt daraxti
2) Kruskal Algoritmi
3) Kruskal algoritmini c++ da amalga oshirish
Minimal daraxt daraxti
Grafning umurtqa pog'onasi daraxt deb ataladi, undan ba'zi qovurg'alarni olib tashlash orqali olish mumkin. Grafda bir nechta magistral daraxtlar bo'lishi mumkin va ko'pincha ularning ko'pi bor.
Rasmda panjara shaklidagi grafikning magistral daraxtlaridan biri (qirralari ko'k rangda ta'kidlangan) ko'rsatilgan.
Og'irlashtirilgan grafikalar uchun magistral daraxtning og'irligi tushunchasi mavjud bo'lib, u magistral daraxtga kiritilgan barcha qirralarning og'irliklari yig'indisi sifatida aniqlanadi. Undan tabiiy ravishda minimal skelet daraxti - minimal mumkin bo'lgan vaznga ega bo'lgan daraxt daraxti tushunchasi kelib chiqadi.
Grafning minimal magistral daraxtini topish uchun ikkita asosiy algoritm mavjud: Prim algoritmi va Kruskal algoritmi. Ularning ikkalasi ham murakkablikka ega O(M log N), shuning uchun, ulardan birini tanlash sizning shaxsiy xohishingizga bog'liq. Ushbu ma'ruzada biz ikkalasini ham tahlil qilamiz.
Kruskal Algoritmi
Kruskal algoritmi uning g'oyasi va amalga oshirilishida juda oddiy. Bu barcha qirralarni uzunlikni oshirish tartibida saralashdan va agar ular turli xil ulanish komponentlarini birlashtirsa, ularni navbat bilan minimal skeletga qo'shishdan iborat.
Rasmiyroq: minimal skeletga kiritilgan ba'zi qovurg'alarni allaqachon topaylik. Turli xil ulanish komponentlarini bog'laydigan barcha qovurg'alar orasida minimal uzunlikdagi qovurg'a minimal skeletga kiritilishi aytiladi.
Kruskal algoritmini amalga oshirish uchun siz qirralarni uzunlik o'sishi bo'yicha saralashingiz kerak (buning uchun biz o'z ma'lumot turimizdan foydalanamiz) va chekka ulanishning ikki xil komponentini birlashtirganligini tekshirishingiz kerak. Buning uchun biz DSU ma'lumotlar strukturasi yordamida joriy ulanish komponentlarini saqlab qolamiz.
Kruskal algoritmining ishlashini vizualizatsiya qilish:
|
| |
