Breadth first search algoritmi

Breadth first search (BFS) algoritmi graph’ning barcha vertex’larini ko’rib chiqishning yana bir yo’li bo’lib, u rekursiv algoritm hisoblanmaydi. BFS Depth first search algoritmidan farqli ravishda queue ishlatadi (DFSstack‘dan foydalanardi).

Algoritmning yana bir hususiyati – u berilgan vertex’dan boshqa vertex’largacha bo’lgan eng qisqa yo’lni topa oladi.

BFS’ning ishlash tartibi quyidagicha:

  • Birinchi vertex tanlanadi.
  • Uning barcha ko’rilmagan vertex’lari ko’rib chiqilib queue’ga qo’shiladi.
  • Birinchi vertex va unga bog’langan vertex’lar ko’rib chiqilgach, queue’dan keyingi vertex o’chiriladi.
  • Keyingi vertex bo’yicha yuqoridagi qadamlar takrorlanadi.

Algoritmning ishlash tartibi (vizualizatsiya)

BFSdagi birinchi amal – birinchi vertex’ni tanlash hisoblanadi. Umuman olganda, biz barcha vertex’larga kirib chiqqanimiz uchun, bizga graph’ning qayeridan boshlash ahamiyatga ega emas. Biz misolimizda A vertex’dan boshlaymiz. A vertex ko’rilgan deb belgilanadi, lekin birinchi vertex bo’lgani uchun queue’ga qo’shilmaydi.

A vertex’ga bog’langan ikki vertex bor – B va G. Ularni queue’ga qo’shamiz va «ko’rilgan» qilib belgilaymiz. Ularni qaysi tartibda qo’shishning ahamiyati yo’q. Esingizda bo’lsa graph uchun api yozganimizda, biz edge’larni Set ichida saqlagandik. Edge’ni o’qib olishda ham Set beradigan edge’lar bo’yicha BFS ishni davom ettiradi.

A ga bog’langan vertex’lar tekshirib bo’lingach, A vertex uchun ish yakunlanadi. Queue’da birinchi B turgani uchun undan ish davom ettiriladi. B queue’dan o’chiriladi.

B ning barcha bog’langan ko’rilmagan vertex’lari queue’ga qo’shiladi. B da bitta ko’rilmagan vertex – C queue’ga qo’shilgach, ko’rilgan qilib belgilanadi.

B ishini tugatadi. Queue’da G birinchi turgani uchun u queue’dan olinib, ish davom ettiriladi.

G ning ikkita ko’rilmagan vertex’i bor: E va J. Ular queue’ga qo’shiladi.

G ishini tugatadi. Queue’da birinchi turgan vertex – C dan ish davom ettiriladi.

C da ko’rilmagan vertex yo’q. C da ish tugaydi. Queue’da E birinchi turgani uchun, E dan davom ettiriladi.

E’ning bitta ko’rilmagan vertex’i – K queue’ga qo’shiladi.

E uchun ish tugaydi. Queue’da keyingi element – J dan ish davom ettiriladi.

J ning barcha ko’rilmagan vertex’lari – D va F queue’ga qo’shiladi.

J ishini yakunlagach, queue’dagi keyingi vertex – K dan davom ettiriladi.

K ning ko’rilmagan vertex’lari yo’q. Queue’dagi keyingi vertex – D dan ish davom ettiriladi.

D da ham ko’rilmagan vertex’lar bo’lmagani uchun, D ga ish to’xtaydi. Queue’dagi keyingi vertex – F dan davom ettiriladi.

F da ko’rilmagan vertex’lar yo’q. Queue bo’shagani uchun ish tugaydi.

Breadth first search algoritmini kodda ifodalash

Graph yasash uchun bizda allaqachon Graph API bor.

Depth first search‘da ko’rilgan vertex’larni marked[] da belgilagan bo’lsak, BFSda ularni distTo[] – path’da qatnashgan vertex’lar sonini kiritib boramiz. Masalan 0 -> 5 bevosita bog’lanish bo’lsa, distTo[5] = 1 bo’ladi.

edgeTo[] ga esa har doimgidek vertex’ga qaysi vertex’dan kelinganini qo’shib boramiz. Shunda edgeTo[w] == v degani, w vertex’ga v vertex’dan kelinganini bildiradi. edgeTo dagi ma’lumotlar asosida biz bir vertex’dan ikkinchi vertex’ga yo’lni topishimiz mumkin.

Quyidagi funksiya deep first search algoritmi asosida berilgan vertex’ga bevosita va bilvosita bog’langan vertex’lar ro’yhatini qaytaradi.

* * *

Manbalar

Breadth-First Search
https://www.coursera.org/learn/algorithms-part2/lecture/DjaET/breadth-first-search

Breadth First Search (BFS) Algorithm Visually Explained
https://levelup.gitconnected.com/breadth-first-search-bfs-algorithm-visually-explained-8dec1f514a6e