8-Laboratoriya ishi Mavzu: Kenglik bo’yicha izlash algoritmi(bfs)

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:
#include
#include
#include


using namespace std;


const int max_n = 100005;
vector<int> g[max_n];
bool used[max_n];//navbatga qo’yilganligini belgilab qo’yadigan mantiqiy oz’garuvch
queue<int> q;//navbat
int d[max_n];


int main() {
int n, m; // Uchlar va bog’lanishlar soni
cin>>n>>m;
for (int i = 1; i <= m; i++) {
int v1, v2;
cin>>v1>>v2;
g[v1].push_back(v2); // Orientrlanmagan graf uchun
g[v2].push_back(v1);
}
q.push(1);// Boshlang'ich uchni navbatga qo'yish
used[1] = 1;
while (!q.empty()) { // Navbatdagi uch bo'sh bo'lmagunga qadar davom ettiramiz
int v = q.front(); // Navbatning boshidagi uchni olamiz
cout<endl;
q.pop(); // Navbatdan uni o'chirib tashlaymiz
for (int i = 0; i < (int)g[v].size(); i++) { // v uchning qo'shnilarini ko'rib chiqamiz
int to = g[v][i]; // v uchning navbatdagi qo'shnisi
if (!used[to]) { // agar u hali ko'rilmagan bo'lsa
used[to] = 1; // uni ko'rilgan uchlar qatoriga qo'shamiz
q.push(to); // uni navbat oxiriga qo'yamiz
d[to] = d[v]+1;
}
}
}
}
Algoritmning ishlashini misolda ko’rib chiqaylik:

Hozir qaralayotgan uch

Navbatga qo’yilgan uch

Navbatdan o’chirilgan uch

Hozir qaralayotgan qirra










Shuning bilan barcha uchlar va barcha bog’lanishlar bir martadan ko’rib chiqiladi. Natijada boshlang’ich uchga bo’g’langan barcha uchlar ko’rib chiqiladi.
Algoritm ishlash vaqti O(n+m). n – uchlar soni, m – bog’lanishlar soni.