|
Algoritmlarni loyihalash fanidan mustaqil ishi
|
| bet | 7/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MI1-misol
BFS algoritmiga misol. Biz ikkita jadvalga ma‘lumotlarni joylashtirib boramiz
Tashrif buyurilgan uchlar – Visited jadvaliga. Navbatda turgan uchlar esa – Queue jadvaliga
2-misol.
Kenglik bo'yicha birinchi qidiruv (BFS)-bu graflar bilan ishlashning ko'plab muhim algoritmlari uchun asos bo'lgan, eng oddiy grafni o'tish algoritmlaridan biri.
Keling, "Eni boʻyicha qidirish" algoritmi qanday ishlashini misol bilan ko'rib chiqaylik. Biz 5 ta uchga ega bo'lgan yo'naltirilmagan grafdan foydalanamiz.
Biz 0 uchdan boshlaymiz, BFS algoritmi uni tashrif buyurilganlar ro'yxatiga qo'yib, uning yonidagi barcha uchlarni stekga qo'yishdan boshlanadi.
Keyinchalik, biz navbatning old qismidagi elementga tashrif buyuramiz, ya'ni 1 va uning yonidagi uchlarga o'tamiz. 0 tashrif buyurilgani uchun biz uning o'rniga 2 ga tashrif buyuramiz.
2-uchda ko'rilmagan qo'shni 4-uch bor, shuning uchun biz uni navbatning orqa qismiga qo'shamiz va navbatning oldida joylashgan 3 - ga tashrif buyuramiz.
Navbatda faqat 4-uch qoladi, chunki qo'shni yagona 3-uch 3, ya'ni 0 ga tashrif buyurilgan. Biz unga tashrif buyuramiz
3-misol. DFS algoritmining ishlashi
Biz 0 uchdan boshlaymiz, DFS algoritmi uni tashrif buyurilgan ro'yxatga qo'yishdan va barcha qo'shni uchlarni stekka joylashtirishdan boshlanadi
Keyin biz 1-uchning yuqori qismidagi elementga tashrif buyuramiz va qo'shni uchlarga o'tamiz. Biz allaqachon 0 ga tashrif buyurganimiz uchun, uning o'rniga 2 ga tashrif buyuramiz.
2-uchda ko'rilmagan qo'shni 4-uch bor, shuning uchun biz uni to'plamning yuqori qismiga qo'shamiz va tashrif buyuramiz
Oxirgi 3-bandga tashrif buyurganimizdan so'ng, uning ko'zga ko'rinmas qo'shni uchlar yo'q. Bu grafni birinchi chuqurlik birinchi o'tishini yakunlaydi.
|
| |
