Guruh talabasi Karimov Doston 8-laboratoriya ishi Mavzu: Kenglik bo’yicha izlash algoritmi(bfs)

912-19 guruh talabasi

Karimov Doston

8-laboratoriya ishi

Mavzu: Kenglik bo’yicha izlash algoritmi(bfs).

Kenglik bo’yicha izlash algoritmi grafni o’tib chiqish va yo’l izlash metodi hisoblanadi. Bizga graf uchlar va bog’lanishlar to’plamlari sifatida beriladi. Yana boshlang’ich uch va oxirgi uch(maqsad uch) beriladi. Boshlang’ich uchdan ohirg uchga boradigan eng qisqa yo’lni topish kerak.

Kenglik bo’yicha izlash algoritmida barcha uchlar grafning alohida sathlariga ajratiladi va bu sathdagi uchlar ketma-ket ko’rib chiqiladi. Qidiruv qandaydir boshlang’ich uch orqali boshlanadi. Qidiruv v uchga kelgan vaqtida unga qo’shni bo’lgan barcha uchlarni ko’rib chiqamiz. Agar qo’shni uch hali ko’rilmagan bo’lsa bu uchni navbatga qo’yamiz.

Kenglik bo’yicha izlash algoritmi quyidagi tartibda bo’ladi(noformal tavsifi):

1. 
   Qidiruv boshlanadigan dastlabki uchni bo’sh bo’lgan navbatga joylashtiramiz.
   
2. 
   Navbatdagi birinchi uchni olamiz va uni navbatdan o’chirib tashlaymiz
   
3. 
   Navbatdan olingan uchga qo’shni bo’lgan barcha uchlarni ko’rib chiqamiz. Agar u hali ko’rilmagan bo’lsa bu uchni ko’rilgan uchlar qatoriga qo’shamiz va bu uchning o’zini navbat oxiriga qo’shamiz.
   
4. 
   Agar navbat bo’sh bo’lsa boshlang’ich uch orqali yetib borib bo’ladigan barcha uchlar ko’rib chiqilib bo’lingan bo’ladi va qidiruvni to’xtatishimiz mumkin.
   

Bu algoritmning C++ dagi kodi: