BFS algoritmi . Tasvirdan koʻrinib turibdiki, algoritmning oʻzi juda
ahamiyatsiz. Tashrif uchun uchlar navbati saqlanib qoladi. Keyingi
uchga tashrif buyurganida, hali tashrif buyurmagan va hali navbatda
boʻlmagan barcha qoʻshnilari navbatga qoʻshiladi. Uchga allaqachon
tashrif buyurilganligini tekshirish uchun bir qator yorliqlardan
foydalaniladi. Dastlab, boshlangʻich uchdan tashqari barcha i uchun
visited[i] = false qiymatini qabul qiladi. i uch visited[i] navbatiga
qoʻshilganda, true qiymati tayinlanadi.
#include using namespace std; vector graph[100000]; bool used[100000]; int main() { //Grafni kiritish // ... Bu qismda graf matritsa koʻrinishida kiritiladi queue q; q.push(0); used[0] = true; while (!q.empty()) { int cur = q.front(); q.pop(); cout << "BFS : " << cur + 1 << endl;
97
for (int k: graph[cur]) { if (!used[k]) { q.push(k); used[k] = true; } } } } Ushbu algoritmning murakkabligi O(n
2
), bu yerda n - grafdagi
uchlar soni. Darhaqiqat, har bir uch ochilib, navbatga bir martagina
joylashtirilgan, shuning uchun navbatning uchlari orasidagi sikl n
martadan koʻp boʻlmagan vaqtda bajariladi. while sikli grafning barcha
uchlari siklni oʻz ichiga oladi va u n marta bajariladi. Agar biz graf
tasvirni qoʻshnilik roʻyxati shaklida ishlatsak, unda murakkablik
O(n+m) boʻladi, bu yerda m - qirralarning soni.
7.2. Grafda oʻtish boʻyi boʻyicha qidiruv (DFS) algoritmi Grafda oʻtish boʻyi boʻyicha qidiruv (DFS) - bu graf uchlaridan
oʻtishning rekursiv algoritmi. Agar boʻyi boʻyicha birinchi qidirish usuli
nosimmetrik tarzda bajarilgan boʻlsa (grafning uchlari darajalar boʻyicha
koʻrib chiqilgan boʻlsa), unda bu usul iloji boricha chuqurroq harakat
qilishni oʻz ichiga oladi. Keyingi rivojlanishning mumkin emasligi
shundan iboratki, keyingi qadam harakatlanishning bir nechta variantiga
ega boʻlgan (ulardan biri toʻliq oʻrganib chiqilgan), ilgari tashrif
buyurgan uch oxirgisiga oʻtish boʻladi.
Algoritm qanday ishlashini aniq bir misol yordamida koʻrib
chiqamiz. Quyidagi yoʻnaltirilmagan bogʻlangan grafda jami 5 ta uch
mavjud. Avval siz boshlangʻich uchni tanlashingiz kerak. Qaysi uch
tanlangan boʻlsa ham, har qanday holatda ham graf toʻliq oʻrganib
chiqiladi, chunki yuqorida aytib oʻtilganidek, bu bitta yoʻnaltirilmagan
bogʻlangan graf. Oʻtish 1 tugundan boshlasin, u holda qarab chiqilgan
tugunlar ketma-ketligi tartibi quyidagicha boʻladi: 1 2 3 5 4. Agar ijro,
98
masalan, 3 tugundan boshlangan boʻlsa, u holda oʻtish tartibi boshqacha
boʻladi: 3 2 1 5 4.
DFS algoritmi rekursiyaga asoslangan, ya‘ni oʻtish funksiyasi oʻzini
bajarilayotganda chaqiradi, bu esa kodni umuman ixcham qiladi.
Algoritmning psevdokodi quyidagicha
