|
tartiblangan to'plamni yarating S grafikdagi barcha qirralarni o'z ichiga olgan
|
| bet | 4/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 suntartiblangan to'plamni yarating S grafikdagi barcha qirralarni o'z ichiga olgan esa S bo'ladi bo'sh emas va F hali emas spanning minimal og'irlikdagi chekkani olib tashlang S agar olib tashlangan chekka ikki xil daraxtni bog'lasa, uni o'rmonga qo'shing F, ikkita daraxtni bitta daraxtga birlashtirish Algoritm tugagandan so'ng, o'rmon grafikning minimal o'rmonini hosil qiladi. Agar grafik ulangan bo'lsa, o'rmon bitta komponentga ega va minimal daraxt daraxtini hosil qiladi. Psevdokod[tahrirlash]
Kruskal algoritmi uchun demo to'liq grafik Evklid masofasiga asoslangan og'irliklar bilan. Quyidagi kod a bilan amalga oshiriladi disjoint-set ma'lumotlar tuzilishi. Bu erda biz o'rmonimizni ifodalaymiz F ikki tepalikning bir daraxtning bir qismi ekanligini samarali aniqlash uchun ajratilgan ma'lumotlar tuzilmasidan foydalaning. algoritm Kruskal(G) bo'ladi F: = o ' zbekistonda har biri uchun v ∈ G. V qil Qilish (v) har biri uchun (u, v) yilda G. e og'irligi bo'yicha buyurtma qilingan (u, v), ortib bormoqda qil agar Topish-to'plam (u) va topish-to'plam (v) keyin := F F ∪ {(u, v)} ∪ {(, u v)} Birlashma (topish-o'rnatish( u), topish-o'rnatish (v)) qaytish F Murakkablik[tahrir] Bilan grafik uchun e qirralar va V tepaliklar, Kruskal algoritmining ishlashini ko'rsatish mumkin O(E log E) vaqt, yoki teng ravishda, O(E log V) vaqt, barchasi oddiy ma'lumotlar tuzilmalari bilan. Ushbu ish vaqtlariko'p va log�2=2log�∈�(log�). Har bir izolyatsiya qilingan vertex minimal o'rmonning alohida komponentidir. Biz izolyatsiya qilingan uchlari e'tiborsizlik bo'lsa, biz olish V R 2 E, shunday log V bo'ladi . Biz bu chegaraga quyidagicha erishishimiz mumkin: avval o(e log E) vaqt ichida taqqoslash navi yordamida qirralarni og'irlik bo'yicha saralash; bu "s dan minimal og'irlikdagi chekkani olib tashlash" qadamiga doimiy vaqt ichida ishlashga imkon beradi. Keyinchalik, qaysi tepaliklarda qaysi komponentlar borligini kuzatib borish uchun ajratilgan ma'lumotlar tuzilmasidan foydalanamiz. Biz har bir vertexni o(V) operatsiyalarini bajaradigan o'zining ajratilgan to'plamiga joylashtiramiz. Va nihoyat, eng yomon holatda, biz barcha qirralarni takrorlashimiz kerak va har bir chekka uchun ikkita 'topish' operatsiyasini va ehtimol bitta birlashmani bajarishimiz kerak. Kabi oddiy ajratilgan ma'lumotlar tuzilishi ham ajratilgan o'rmonlar daraja bo'yicha birlashma bilan o (E) operatsiyalarini bajarishi mumkin O(E log V) vaqt. Shunday qilib, umumiy vaqt O(e log E) = O(E log V). Agar qirralar allaqachon saralangan bo'lsa yoki chiziqli vaqt ichida saralanishi mumkin bo'lsa (masalan, bilan hisoblash saralash yoki radix saralash), algoritm ishlash uchun yanada murakkab ajratilgan ma'lumotlar tuzilmasidan foydalanishi mumkin O(E.) (V)) vaqt, bu erda D. ning juda sekin o'sib borayotgan teskari tomoni. yagona-qimmatli Ackermann funktsiyasi. Misol[tahrir]
|
| |
