|
Kruskal algoritmini bosqichma-bosqich bajarish
|
| bet | 3/4 | | Sana | 18.05.2024 | | Hajmi | 221,49 Kb. | | #243271 | | Turi | Referat |
Bog'liq Algoritm-ReferatKruskal algoritmini bosqichma-bosqich bajarish
1. Chetlarni saralash
Kruskal algoritmini bajarishda birinchi qadam grafikning barcha qirralarini ularning vazni yoki narxiga qarab o'sish tartibida saralashdir. Ushbu saralash jarayoni algoritmning o'sib borayotgan minimal kenglikdagi daraxtga (MST) qo'shish uchun eng arzon mavjud qirralarni samarali aniqlashini ta'minlaydi. Eng kam og'irliklarga ega bo'lgan qirralarga ustunlik berib, Kruskal algoritmi oxir-oqibat optimal MSTga olib keladigan ochko'z qarorlar qabul qilishi mumkin.
2. Chet tanlash
Kenarlarni saralagandan so'ng, Kruskal algoritmi tartiblangan ro'yxat bo'ylab har bir chekkani birma-bir ko'rib chiqadi. Har bir chekka uchun algoritm ushbu chekkani joriy MSTga qo'shish sikl hosil qiladimi yoki yo'qligini tekshiradi. Agar chekka qo'shilishi tsiklni kiritmasa, algoritm MSTga chekka qo'shadi. Qirralarni baholash va tanlab qo'shishning bosqichma-bosqich jarayoni grafikdagi barcha cho'qqilar ulanmaguncha davom etadi va to'liq minimal kenglik daraxtini hosil qiladi.
3. Tsiklni aniqlash va undan qochish
Kruskal algoritmining muhim jihati uning o'sib borayotgan MSTda tsikllarni yaratishni aniqlash va oldini olish qobiliyatidir. Har bir potentsial chekka qo'shimchasini sinchkovlik bilan o'rganib chiqib, algoritm yakuniy MSTning asiklik bo'lishini ta'minlaydi, chunki bu daraxtning ta'rifi talab qilinadi. Ushbu siklni aniqlash mexanizmi odatda Union-Find ma'lumotlar strukturasi deb ataladigan ma'lumotlar strukturasi yordamida amalga oshiriladi, bu cho'qqilarning ulanishini samarali kuzatib boradi va algoritmga MSTga qaysi qirralarni kiritish haqida qaror qabul qilishga yordam beradi.
Kruskal algoritmining vaqt murakkabligi tahlili
Kruskal algoritmining vaqt murakkabligi tahlili uning samaradorligi va turli muammolar sohalari uchun mosligini baholashda muhim ahamiyatga ega. Algoritmning umumiy ishlashi, birinchi navbatda, chekkalarni saralash uchun zarur bo'lgan vaqtga va tsiklni aniqlash uchun foydalaniladigan Union-Find ma'lumotlar strukturasining samaradorligiga bog'liq.
Kruskal algoritmining vaqt murakkabligini quyidagi asosiy bosqichlarga bo'lish mumkin:
|
| |
