4-amaliy mashg’uloti. Bog'langan ro'yxat. Saralash masalalari. Qidiruv usullari. Daraxtlar bilan ishlash masalalari. Graflar: nazariya asoslari, algoritmlar
Download 213.5 Kb.
|
4-amaliy ish
- Bu sahifa navigatsiya:
- GRAFLARDA KENGLIK BO’YICHA QIDIRISH
GRAF CHUQURLIGINI QIDIRISH
Endi biz kodda grafiklarni qanday taqdim etishni o'rgandik, o'rganishni boshlashimiz mumkin grafiklardagi ba'zi algoritmlar! Chuqur qidirish (DFS) bilan boshlaymiz va qidirish bilan yakunlaymiz kengligi (bfs). Maqolani chalkashtirib yubormaslik uchun yo'l qidirish algoritmlari bu erda bo'lmaydi ko'rib chiqiladi. Chuqur qidirish grafikalardagi asosiy algoritmlardan biridir. U quyidagilar uchun ishlatiladi grafadagi bir tepalikdan boshqa tepaliklarga masofani topish. Bu aylanib o'tish algoritmi. Chuqurlikdagi qidiruv har bir tepalikni ikkita yorliqdan birining grafigida belgilaydi: tashrif buyurilgan yoki tashrif buyurilmagan. Algoritm, agar iloji bo'lsa, har bir vertexni tashrif buyurilgan deb belgilaydi tsikllardan saqlaning. U quyidagicha ishlaydi: 1. Grafikning har qanday tepasini stekka qo'ying. 2. Biz stekdan elementni olamiz va uni tashrif buyurganlar ro'yxatiga qo'shamiz. 3. Ushbu tepalikning qo'shnilari ro'yxatini yarating. Ichida bo'lmaganlarni stekka qo'shing, ya’ni tashrif buyurilganlar ro'yxatini. 4. Stek bo'sh bo'lguncha 2 va 3-bandlarni takrorlang. Qidiruv algoritmining chuqur vizual ko'rinishi. Qidiruv 1-cho’qqida boshlanadi. GRAFLARDA KENGLIK BO’YICHA QIDIRISH Kenglikni qidirish-bu grafikalarni chetlab o'tishning yana bir algoritmi. Qidiruv algoritmi bilan birgalikda ichkariga qarab, u qiziqarli dasturlash musobaqalarining ko'p qismini tashkil qiladi, hech bo'lmaganda grafikalar bilan bog'liq bo'lganlar. Kenglikni qidirish, shuningdek, grafadagi har bir tepalikni ikkita toifadan biriga joylashtiradi: tashrif buyurilgan yoki tashrif buyurilmagan. Va ikkala algoritmning maqsadi bir xil: har birini belgilang agar ko'chadan qochish mumkin bo'lsa, grafadagi cho’qqi tashrif buyurilgan. Algoritm qanday ishlaydi kenglik bo’yicha qidirish: 1. Har qanday tepalikni navbatning oxiriga qo'ying. 2. Biz navbatning boshida elementni olamiz va uni tashrif buyurganlar ro'yxatiga qo'shamiz. 3. Ushbu tepalikning qo'shnilari ro'yxatini yarating. Chiziqning oxiriga qo'shing tashrif buyurmaganlar. 4. Navbat bo'sh bo'lguncha 2 va 3-bandlarni takrorlang. Ko'rib turganingizdek, keng qidirish algoritmi chuqur qidirish algoritmiga juda o'xshaydi. Biroq, algoritm kabi grafik yoki daraxt shoxidan pastga tushish o'rniga Chuqurlik bo’yicha qidirish, kenglik bo’yicha qidirish algoritmi har bir darajadan o'tadi. void bfs(int u){ queue q.push(u); v[u] = true; while (!q.empty()) { int f = q.front(); q.pop(); // Ставим в очередь все соседние F и помечаем их как посещённые for (auto i = g[f].begin(); i != g[f].end(); i++) { if (!v[*i]) { q.push(*i); v[*i] = true; } } } } Download 213.5 Kb. Do'stlaringiz bilan baham: |
Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling
ma'muriyatiga murojaat qiling