|
Grafda oʻtish eni boʻyicha qidiruv- BFS algoritmi
|
| bet | 5/10 | | Sana | 27.05.2024 | | Hajmi | 0,61 Mb. | | #254553 |
Bog'liq algoritm.MIGrafda oʻtish eni boʻyicha qidiruv- BFS algoritmi
G = (V, E) grafi berilgan boʻlsin va boshlangʻich uchi tanlansin. Birinchi kenglik boʻyicha qidirish algoritmi v uchga yetib boruvchi barcha uchlarni "ochish" uchun G grafning barcha qirralarini muntazam ravishda kesib oʻtadi. Oʻtish jarayonida barcha uchlarni oʻz ichiga olgan dastlabki uchda joylashgan kenglik boʻyicha qidiruv daraxtini yaratadi. E‘tibor bering, ildiz uchidan ushbu daraxtning istalgan uchiga masofa (qirralarning soni) eng qisqa boʻladi.
Kenglik boʻyicha birinchi qidiruv ushbu nomga ega, chunki grafni bosib oʻtish jarayonida k+1 masofadagi har qanday uchni qayta ishlashdan oldin k masofadagi barcha uchlar belgilanadi.
Algoritm ham yoʻnaltirilgan, ham yoʻnaltirilmagan graflar uchun ishlaydi. Algoritm gʻoyasi: birinchisiga tutash boʻlgan barcha uchlar ochiladi, ya‘ni ular roʻyxatga joylashtiriladi va bitta belgini oladi. Shundan soʻng, dastlabki uch toʻliq qayta ishlanadi va 2 bilan belgilanadi.
Roʻyxatning birinchi yuqori qismi keyingi uchga aylanadi. Amaldagi bilan qoʻshni boʻlgan avval belgilanmagan barcha uchning roʻyxatning oxiriga qoʻshiladi (ochiladi). Joriy uch roʻyxatdan oʻchirilib, 2 raqami bilan belgilanadi. Jarayon uchlar roʻyxati boʻsh boʻlguncha davom etadi. Ma‘lumotlar roʻyxatining ushbu koʻrinishi navbat deyiladi.
10-rasm. BFS algoritmi jarayonida graf uchlarini koʻrish
BFS algoritmi. Tasvirdan koʻrinib turibdiki, algoritmning oʻzi juda ahamiyatsiz. Tashrif uchun uchlar navbati saqlanib qoladi. Keyingi uchga tashrif buyurganida, hali tashrif buyurmagan va hali navbatda boʻlmagan barcha qoʻshnilari navbatga qoʻshiladi. Uchga allaqachon tashrif buyurilganligini tekshirish uchun bir qator yorliqlardan foydalaniladi. Dastlab, boshlangʻich uchdan tashqari barcha i uchun visited[i] = false qiymatini qabul qiladi. i uch visited[i] navbatiga qoʻshilganda, true qiymati tayinlanadi.
#include
using namespace std;
vector graph[100000];
bool used[100000];
int main()
{
//Grafni kiritish
// ... Bu qismda graf matritsa koʻrinishida kiritiladi
Queue q;
q.push(0);
used[0] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
cout << "BFS : " << cur + 1 << endl;
for (int k: graph[cur]) {
if (!used[k]) {
q.push(k);
used[k] = true;
}
}
}
}
Ushbu algoritmning murakkabligi O(n2 ), bu yerda n - grafdagi uchlar soni. Darhaqiqat, har bir uch ochilib, navbatga bir martagina joylashtirilgan, shuning uchun navbatning uchlari orasidagi sikl n martadan koʻp boʻlmagan vaqtda bajariladi. while sikli grafning barcha uchlari siklni oʻz ichiga oladi va u n marta bajariladi. Agar biz graf tasvirni qoʻshnilik roʻyxati shaklida ishlatsak, unda murakkablik O(n+m) boʻladi, bu yerda m - qirralarning soni.
|
| |
