Amaliy ish №6. Graflar: nazariya asoslari, algoritmlar qidiruv

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;
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;
}
}
}
}