الگوریتم پیمایش اول سطح یا جستجوی اول سطح (Breadth
First Search - BFS) از جمله الگوریتم‌های مشهور پیمایش و جستجوی گراف است که در حل
مسائل الگوریتمی و هوش مصنوعی کاربرد دارد. این الگوریتم برای پیمایش و جستجوی گراف
از یک صف برای نگهداری ترتیب جستجو استفاده می‌کند.
الگوریتم BFS با وارد کردن گره مبدأ به صف پردازش شروع
شده و تا خالی نشدن این صف مراحل زیر را تکرار می‌شود:
1- عنصر جلوی صف را به عنوان گره جاری انتخاب و از صف حذف
کن.
2- گره جاری را پردازش کن.
3- گره‌های مجاور گره جاری که پردازش نشده و در صف پردازش
نیز قرار ندارند به این صف اضافه کن.
منظور از پردازش، هر عملی روی گره است که پیمایش یا جستجو
به آن نیت صورت گرفته است.
به عنوان مثال در گراف زیر:
ترتیب پیمایش گره‌ها با شروع از گره شماره 1 به این ترتیب
خواهد بود:
1, 2, 3, 4, 8, 7, 5, 6
دلیل نام‌گذاری این روش با عبارت «اول سطح» در پیمایش یک
درخت از ریشه مشخص می‌شود که گره‌ها به صورت سطح به سطح پیمایش می‌شوند و اولویت
پیمایش با سطح گره است. به همین دلیل به این الگوریتم «پیمایش سطحی» یا «پیمایش سطح
اول» نیز گفته می‌شود.
نکته: ممکن است هدف از اجرای الگوریتم
BFS یافتن یک گره با مشخصات خاص در گراف باشد. در این حالت گره مذکور (در صورت
وجود) ممکن است زودتر از خالی شدن صف پردازش یافت شده و نیازی به ادامه الگوریتم و
پیمایش سایر گره‌ها نباشد.
پیاده‌سازی الگوریتم جستجوی اول سطح
[برگرد بالا]
تابع bfs یک پیاده‌سازی ساده از الگوریتم BFS به زبان
برنامهنویسی ++C است که با دریافت مشخصات گراف و شماره اندیس گره مبدأ، گراف را
پیمایش کرده و شماره عدد هر گره را به عنوان پردازش آن چاپ می‌کند:
void bfs(int
graph[MAX][MAX], int numberOfNodes, int
sourceNode){
queue<int>
processQueue;
bool visited[MAX] = {
false };
processQueue.push(sourceNode);
visited[sourceNode] =
true;
while(!processQueue.empty()){
int
currentNode = processQueue.front();
processQueue.pop();
cout << currentNode + 1
<< "\t" << endl;
for(int
i = 0 ; i < numberOfNodes ; i++)
if(graph[currentNode][i]
< INT_MAX && !visited[i]){
processQueue.push(i);
visited[i] =
true;
}
}
}
این تابع با استفاده از آرایه visited قرار گرفتن گره در
صف و پردازش آن را مشخص می‌کند. حلقه for بررسی یال‌های مجاور گره جاری برای اضافه
شدن به صف را بر عهده داشته و حلقه while تا زمان خالی شدن صف تکرار می‌شود.
مرتبه زمانی الگوریتم جستجوی اول
سطح
[برگرد بالا]
در گراف (G = (V, E مرتبه زمانی الگوریتم جستجوی اول سطح
(|O(|V| + |E است؛ چرا که این الگوریتم در بزرگترین حالت تمامی گره‌ها را پیمایش
کرده و نیاز به بررسی تمامی یال‌ها دارد. این مرتبه اجرایی در یک گراف همبند به
صورت (|O(|E بوده (چرا؟) و در حالت کلی متناسب با تعداد یال‌ها حداکثر از مرتبه
(O(n2 است.
کاربردهای الگوریتم جستجوی اول سطح
[برگرد بالا]
یک کاربرد مهم الگوریتم BFS تشخیص همبندی گراف یا
مؤلفه‌های همبندی آن است. اگر نتیجه پیمایش گراف با این الگوریتم شامل تمامی
گره‌های آن باشد، به معنی همبند بودن گراف است؛ اما اگر اینگونه نباشد، متناسب با
جهت‌دار بودن یا نبودن گراف نتیجه مختلفی برداشت می‌شود. این حالت در گراف بدون جهت
به معنی ناهمبند بودن گراف بوده و در گراف جهت‌دار صرفا می‌توان مطمئن شد که گراف
قویا همبند نیست. اگر در پیمایش به وسیله BFS از یک گره مشخص تمامی گره‌ها بازدید
نشوند، می‌توان با گره دیگری خارج از گره‌های بازدید شده قبلی الگوریتم را مجددا
تکرار کرده و به یک مؤلفه همبندی دیگر رسید. در گراف جهت‌دار ممکن است گره‌های جدید
با گره‌های بازدید شده قبلی اشتراک داشته باشند که نشان از وجود مسیرهایی از بخش
دوم به بخش اول دارد؛ اما به طور حتم هیچ‌کدام از این مسیرها دو طرفه نیستند.
کاربرد دیگری از الگوریتم BFS تولید یک درخت پوشا برای
گراف است. اگر هر گره پیمایش شده در الگوریتم BFS را به گره‌هایی که توسط آن وارد
صف می‌شوند متصل کنیم، یک درخت پوشا از مجموعه آن گره‌ها تولید می‌شود. اگر گراف
همبند باشد، درخت حاصل درخت پوشای کل گراف خواهد بود. تکرار این کار روی مؤلفه‌های
همبندی یک گراف ناهمبند نیز یک جنگل از درخت‌های پوشای محلی تولید می‌کند.
تذکر: درخت پوشای تولید شده با الگوریتم
BFS برای یک گراف وزن‌دار لزوما درخت پوشای کمینه نیست.
کاربرد دیگر الگوریتم BFS برای پیمایش صفحات مارپیچ
(Maze) است که در بازی‌ها و همینطور مباحث رباتیک برای تشخیص مسیر بسیار کاربرد
دارد. یک صفحه مشبک را در نظر بگیرید که دو ربات (موش) و چند خانه هدف (پنیر) در یک
محوطه محصور توسط موانع قرار دارند:
هدف برنامهنویسی ربات‌های موش برای جمع کردن پنیرهای
موجود است. ربات تنها مجاز به حرکت از هر خانه به چهار خانه مجاور خود در صورت نبود
مانع است. چنین ساختاری با گراف قابل شبیه‌سازی است؛ به این ترتیب که هر خانه یک
گره در نظر گرفته شده و خانه‌های مجاور در صفحه با یال به هم متصل می‌شوند. این
مثال ساده نشان از گراف بدون جهتی دارد که هزینه حرکت از هر گره به گره‌های مجاور
خود ثابت و برای هر دو گره مجاور یکسان است. بنابراین می‌توان آن را به صورت گراف
بدون وزن در نظر گرفت. درخت پوشای تولید شده با الگوریتم BFS از محل شروع حرکت
ربات، کوتاهترین مسیر حرکت به هر هدف را مشخص کرده و امکان تشخیص نزدیکترین هدف را
فراهم می‌کند.
تذکر: در الگوریتم جستجوی اول سطح جهت
یال‌ها مهم بوده، اما وزن یال‌ها هیچ نقشی ندارند. ممکن است متناسب با نیاز، معیار
وزن به طریقی در الگوریتم وارد شود؛ به عنوان مثال گره‌ها به ترتیب وزنشان وارد صف
شده و پیمایش شوند؛ اما چنین قانونی در ذات این الگوریتم وجود ندارد. استفاده از
این الگوریتم در maze به خاطر بدون وزن بودن گراف معادل صفحه است. به عبارت دیگر،
هزینه حرکت از یک گره به گره دیگر برابر تعداد یال‌های مسیر است. اگر یال‌ها
وزن‌دار باشند، مسیر مشخص شده توسط این الگوریتم لزوما کم‌هزینه‌ترین مسیر نیست.
الگوریتم دایکسترا نمونه‌ای از راهکاری مبتنی بر پیمایش BFS است
که کوتاهترین مسیر در گراف‌های وزن‌دار با وزن‌های متنوع را مشخص می‌کند.