|
Grafda oʻtish eni boʻyicha qidiruv- BFS algoritmiBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARI
7.1. Grafda 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.
Quyidagi misolni koʻrib chiqamiz (27-rasm). 27-a) rasmda grafning
dastlabki koʻrinishi berilgan. 27-b) rasmda, uchlar yonida, graf uchlarini
koʻrish tartibi qavsda koʻrsatilgan. Breadth First Search (BFS) daraxtini
hosil qiladigan qirralar qalin rangda berilgan.
96
a)
b)
27-rasm. BFS algoritmi jarayonida graf uchlarini koʻrish
|
| |
