Kenglik bo‘yicha qidiruv (BFS)

Kenglik bo‘yicha qidiruv (BFS) haqida bilib oling

Kirish

Kenglik bo‘yicha qidiruv (BFS) algoritmi og‘irliksiz grafda ishlaydi va manba cho‘qqi $s$ dan boshlanadi.

Graf yo‘naltirilgan ham, yo‘naltirilmagan ham bo‘lishi mumkin — BFS har ikkala holatda ham ishlaydi.

BFS ni tasavvur qilishning yaxshi usuli — graf bo‘ylab olovning tarqalishi:

• $0$-qadamda faqat manba cho‘qqi $s$ “yonadi”;
• har bir keyingi qadamda olov hozir yonayotgan barcha cho‘qqilardan ularning qo‘shnilariga tarqaladi.

Shunday qilib, bitta iteratsiyada “olov halqasi” bitta qirra bo‘yicha kengayadi. Aynan shu sababli BFS cho‘qqilarni manbadan masofa ortib borish tartibida ko‘radi.

G‘oya

BFS ni amalga oshirish uchun biz quyidagilardan foydalanamiz:

• qayta ishlanishi kerak bo‘lgan cho‘qqilarni saqlaydigan navbat q;
• used[x] massivi, u x cho‘qqi allaqachon ko‘rilganmi-yo‘qmi ko‘rsatadi.

Dastlab:

• manba cho‘qqi s ni navbatga qo‘yamiz;
• uni ko‘rilgan deb belgilaymiz;
• qolgan barcha cho‘qqilarni ko‘rilmagan deb belgilaymiz.

So‘ng, navbat bo‘sh bo‘lmaguncha:

1. navbatning oldidagi cho‘qqini olamiz;
2. uning barcha qo‘shnilarini ko‘rib chiqamiz;
3. agar qo‘shni hali ko‘rilmagan bo‘lsa, uni ko‘rilgan deb belgilaymiz va navbatga qo‘shamiz.

Algoritm oxirida s dan yetib borish mumkin bo‘lgan barcha cho‘qqilar ko‘rilgan bo‘ladi.

Eng qisqa yo‘llar

BFS ning eng muhim xossalaridan biri shundaki, og‘irliksiz grafda u manbadan har bir yetib boriladigan cho‘qqigacha ni topadi.