Algoritmdan nazorat savollariga javoblar Algoritm nima

#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.

Qo’llanilishi:

1. 
   Grafning komponentalarni aniqlash. Buning uchun navbatdagi hali ko’rilmagan uch orqali kenglik bo’yicha izlashni boshlaymiz. Bu o’tib chiqishda u unga bog’langan barcha uch orqali o’tib chiqadi, va ular bitta graf komponentasi deb aytiladi. Komponentalar soni bfs funksiyasiga necha marta murojaat qilganimiz soni. used massivida true qiymatni qabul qilgan barcha uchlar kenglik bo’yicha izlashni boshlagan uch orqali borib bo’ladi.
   
2.