یکی از الگوریتم‌هایی که کاربرد زیاد و کارایی بالایی در برای کاوش و پیمایش گراف‌ها داره، الگوریتم جستجوی اول سطح (BFS) هست. توانایی این الگوریتم در یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن، باعث شده الگوریتم جستجوی اول سطح، کاربردهای زیادی در علوم رایانه و حوزه‌های مرتبط پیدا کنه. در این مقاله قصد داریم با تعریف الگوریتم BFS، مزیت‌های این الگوریتم و مراحل مختلف پیاده‌سازی اون، بیشتر آشنا بشیم. پس اگر قصد دارین با مفاهیم کلی یکی از پرکاربردترین الگوریتم‌ها در حوزه پیمایش گراف‌ها آشنا بشین، این مقاله‌ی آموزش برنامه نویسی را در بلاگ کندو تا پایان مطالعه کنین.
الگوریتم پیمایش گراف چیه؟
پیمایش گراف، یک تکنیک جستجو برای یافتن رأس در یک گراف هست. پیمایش گراف در فرآیند جستجو برای تعیین ترتیب بازدید از رئوس به‌وسیله الگوریتم، استفاده می‌شه. پیمایش گراف بدون ایجاد لوپ (حلقه)، لبه‌های موردنظر رو در فرآیند جستجو، پیدا می‌کنه. یعنی شما با استفاده از پیمایش گراف می‌تونین تمامی رئوس گراف رو بدون طی کردن یک مسیر حلقه وار، مشاهده کنین.
دو روش کلی برای پیمایش گراف‌ها وجود داره:
- روش جستجوی اول سطح یا الگوریتم BFS
- روش پیمایش عمق اول یا الگوریتم DFS
حالا قراره بیشتر با الگوریتم جستجوی اول سطح یا BFS آشنا بشیم.
بیشتر بخوانید: آموزش الگوریتم و فلوچارت {راهنمای جامع آموزشی}
الگوریتم جستجوی اول سطح چیه؟
الگوریتم BFS، جزو پرکاربردترین الگوریتم‌ها به‌حساب می یاد. BFS، یک رویکرد پیمایش گراف هست که شما می‌تونین ابتدا الگوریتم رو با گره مبدأ (منبع) آغاز کنین و بعدش لایه به لایه، گره‌هایی رو که مستقیماً با گره مبدأ ارتباط دارن، تحلیل کنین. شما در مرحله بعد پیمایش BFS، باید گره‌های مجاور سطح بعد رو مشاهده کنین.
پیمایش در جهت عرضی
بر اساس BFS، شما باید گراف رو در جهت عرضی پیمایش کنین:
- برای شروع، به‌صورت افقی حرکت کنین و از کل گره‌های لایه موجود رو بازدید کنین
- بعدش به لایه بعدی حرکت کنین.
نحوه شکل‌گیری صف در الگوریتم BFS
صفر بر اساس اصل اولین ورودی اولین خروجی (FIFO) عمل می‌کنه، یعنی گره‌های مجاور به ترتیب قرارگیری بازدید می‌شن و اولین گره مورد بازدید، اون گرهی هست که قبل از بقیه، قرار داده شده.
نحوه عملکرد الگوریتم BFS
جستجوی اول سطح از ساختار داده صف برای نگهداری گره و بازدید شدن آن تا زمان بازدید از کل رئوس مجاور که ارتباط مستقیمی با اون گره دارن، استفاده می‌کنه. صف هم بر اساس اصل فایفو شکل می‌گیره و اولین گره نمایش داده شده، اون گرهی هست که اول از همه، قرار داده شده. پیمایش الگوریتم BFS در مورد گره‌ها به دو شکل انجام می‌شه:
- گره بازدید شده
- گره بازدید نشده.
ترتیب مراحل اجرای الگوریتم جستجوی اول سطح
- شروع با گره مبدأ (منبع)
- اضافه کردن گره در جلوی صف نسبت به فهرست بازدید شده
- ایجاد فهرستی از گره‌های بازدید شده که در فاصله نزدیکی به آن رأس قرار دارند.
- خارج کردن گره‌های بازدید شده از صف
- تکرار مراحل تا زمان خالی شدن صف
چرا الگوریتم BFS اهمیت داره؟
الگوریتم جستجوی اول سطح، کاربردهای زیادی در پیمایش ساختمان داده گراف داره. تو این قسمت، به بعضی از مهم‌ترین کاربردهای الگوریتم BFS اشاره می‌کنیم:
- معماری ساده و قابل‌اطمینانی داره.
- الگوریتم جستجوی اول سطح باعث کمک به ارزیابی گره‌ها در یک گراف می‌شه و کوتاه‌ترین مسیر رو برای پیمایش گره‌ها، تعیین می‌کنه.
- این الگوریتم، قابلیت پیمایش یک گراف رو در کمترین تعداد تکرارهای ممکن داره.
- تکرارها در الگوریتم BFS، یکنواخت و بدون عیب و نقص انجام می‌شن و این روش هیچ‌وقت، توی یک لوپ نامتناهی گرفتار نمی‌شه.
- نتیجه الگوریتم‌های BFS در مقایسه با الگوریتم‌های دیگه، دقت بالایی داره.
قوانین مهم اجرای الگوریتم
- شما می‌تونین هر گرهی رو به‌عنوان گره مبدأ یا گره ریشه خودتون، انتخاب کنین.
- شما باید تمامی گره‌ها رو پیمایش کنین.
- فراموش نکنین که گره‌های تکراری رو بازدید کنین.
- شما باید گراف رو در جهت عرضی و نه عمقی، پیمایش کنین.
معماری الگوریتم جستجوی اول سطح
مطابق توضیحات قبل، توی شکل زیر، گره‌های الگوریتم BFS در ساختار درختی نشون داده شدن.
دیاگرام درختی بالا، سه تا لایه داره که از 0 تا 7، شماره‌گذاری شدن.
- ما می‌تونیم هر گرهی رو به‌عنوان گره مبدأ خودمون انتخاب کنیم. تو این مثال، گره 0 رو به‌عنوان گره مبدأ انتخاب کردیم.
- توی مرحله بعد، پیمایش رو به‌صورت عرضی انجام می‌دیم و گره‌هایی رو پیدا می‌کنیم که در مجاورت گره مبدأ ما، به این گره متصل شدن.
- اگر شما گره مبدأ دیگه‌ای رو انتخاب کنین، ترتیب عوض می‌شه.
شبه کد الگوریتم جستجوی اول سطح
در این قسمت، شبه کد الگوریتم جستجوی اول سطح رو بیان کردیم:
مثالی از الگوریتم جستجوی اول سطح
در یک ساختار درختی و در پیمایش گراف، هر گره بازدید نشده، مورد بازدید و بررسی قرار می‌گیره. توالی که بازدید گره‌ها هم بر اساس زمان قرارگیری هر گره تعیین می‌شه. الگوریتم BFS با اولین گره ابتدایی در یک گراف آغاز شده و اون گره رو کاملاً پیمایش می‌کنه. پس از پیمایش موفق اولین گره، رأس پیمایش نشده بعدی در گراف، بازدید و علامت زده می‌شه.
مرحله 1: در گراف، هر رأس یا گره معلوم هست. اول صفر تشکیل می‌شه.
مرحله 2: در گراف، ابتدا گره مبدأ A رو در نظر گرفته، این گره رو بازدید می‌کنیم و علامت می‌زنیم.
مرحله 3: سپس شما می‌تونین گره‌های B و E رو مشاهده کنین که در نزدیکی A، بازدید نشدن. شما دو گره در این مثال دارین، اما گره B رو انتخاب می‌کنیم، علامت می‌زنیم و به ترتیب حروف الفبای انگلیسی در صف قرار می‌دیم.
مرحله 4: گره E گره بعدی بازدید نشده در مجاورت گره A است. سپس این گره رو علامت می‌زنیم و توی صف قرار می‌دیم.
مرحله 5: حالا هیچ گره بازدید نشده‌ای اطراف A قرار نداره. درنتیجه A رو از صف خارج می‌کنیم.
مرحله 6: گره C یک گره مجاور و بازدید نشده در نزدیکی گره B است. شما می‌تونین این گره رو پس از بازدید شدن، علامت بزنین.
مرحله 7: گره D، گره مجاور بازدید نشده نسبت به C است. پس از بازدید شدن، این گره رو داخل صف، قرار بدین.
مرحله 8: اگر تمامی گره‌های مجاور D بازدید شده باشن، D رو از صف حذف کنین.
مرحله 9: به‌طور مشابه، کلیه گره‌های نزدیک به E، B و C بازدید شدن؛ بنابراین شما باید تمامی اونها رو از صف بردارین.
مرحله 10: حالا که صف خالی شده، پیمایش BFS به پایان رسیده.
برای آشنایی بیشتر با مبانی برنامه نویسی، در دوره Programming Fundamentals ثبت نام کنید.
پیچیدگی الگوریتم جستجوی اول سطح
پیچیدگی الگوریتم جستجوی اول سطح چطور بررسی می‌شود؟ در ادامه بخوانید.
پیچیدگی زمانی الگوریتم جستجوی اول سطح
می‌شه پیچیدگی زمانی الگوریتم جستجوی اول سطح رو به‌صورت O(|V|+|E|) بیان کرد که توی بدترین حالت، هر رأس و لبه رو پیمایش می‌کنه. تعداد رئوس در گراف |V| و تعداد لبه‌ها، |E| هست.
پیچیدگی فضایی الگوریتم جستجوی اول سطح
می‌تونیم پیچیدگی فضایی رو به‌صورت O(|V|) تعریف کرد که |V|، تعداد رئوس گراف است و ساختارهای داده‌ای متفاوتی برای تعیین نوع رئوس اضافه شده به صف نیاز هستن. همچنین این پیچیدگی نشون دهنده فضای لازم برای گراف هست که بر اساس نمایش گراف‌های مورد استفاده با پیاده‌سازی الگوریتم، تغییر می‌کنه.
کاربردهای الگوریتم BFS
توی این قسمت، کاربردهای الگوریتم جستجوی اول سطح رو بیان کردیم:
گراف‌های بدون وزن
کوتاه‌ترین مسیر در یک گراف بدون وزن، مسیری با کمترین تعداد لبه‌ها هست. شما همیشه از یک منبع مشخص با استفاده از حداقل تعداد لبه‌ها در زمان استفاده از سطح اول، به رأس می‌رسین. در گراف‌های بدون وزن، هر درخت پوشا، یک درخت پوشای کمینه هست و شما می‌تونین یک درخت پوشا رو با استفاده از پیمایش اول سطح یا عمق، شناسایی کنین.
شبکه همتا به همتا
الگوریتم BFS برای کشف کلیه گره‌های مجاور در شبکه‌های همتا به همتا مثل بیت تورنت، استفاده می‌شه.
کراولرها در موتور جستجو
کراولرها، ایندکس‌ها رو بر اساس جستجوی اول، ایجاد می‌کنن. هدف، شروع کار در صفحه اصلی و دنبال کردن تمام لینک‌ها و سپس تکرار هست. همچنین کراولرها می‌تونن از پیمایش اول عمق استفاده کنن. اما مزیت جستجوی اول سطح، امکان محدود شدن عمق یا لایه‌های درخت ایجاد شده هست.
وب‌سایت‌های شبکه اجتماعی
شما می‌تونین از جستجوی اول سطح برای شناسایی اشخاص در یک فاصله مشخص d از یک فرد در شبکه‌های اجتماعی تا سطوح d استفاده کنین.
سیستم ناوبری GPS
می‌تونین از این الگوریتم برای پیدا کردن تمامی مکان‌ها و نواحی نزدیک، استفاده کنین.
جمع‌آوری زباله
تکنیک چینی از جستجوی اول سطح برای جمع‌آوری زباله استفاده می‌کنه. با توجه به مکان‌یابی بهتر، جستجوی اول سطح، بهتر الگوریتم جستجوی اول عمق هست.
شناسایی مسیرها
جهت مشاهده وجود مسیر بین دو رأس، می‌تونین از هر دو روش جستجوی اول سطح یا پیمایش اول عمق استفاده کنین.
پیدا کردن تمامی گره‌ها در یک جزء
برای مکان‌یابی تمامی گره‌های در دسترس نسبت به یک گره خاص، می‌تونین از هر دو روش جستجوی اول سطح یا پیمایش اول عمق استفاده کنین.
پیاده‌سازی کد الگوریتم جستجوی اول سطح
| #include<stdio.h> #include<conio.h> #include<stdlib.h> int twodimarray[10][10],queue[10],visited[10],n,i,j,front=0,rear=-1; void breadthfirstsearch(int vertex) // breadth first search function { for (i=1;i<=n;i++) if(twodimarray[vertex][i] && !visited[i]) queue[++rear]=i; if(front<=rear) { visited[queue[front]]=1; breadthfirstsearch(queue[front++]); } } int main() { int x; printf(“\n Enter the number of vertices:”); scanf(“%d”,&n); for (i=1;i<=n;i++) { queue[i]=0; visited[i]=0; } printf(“\n Enter graph value in form of matrix:\n”); for (i=1;i<=n;i++) for (j=1;j<=n;j++) scanf(“%d”,&twodimarray[i][j]); printf(“\n Enter the source node:”); scanf(“%d”,&x); breadthfirstsearch(x); printf(“\n The nodes which are reachable are:\n”); for (i=1;i<=n;i++) if(visited[i]) printf(“%d\t”,i); else printf(“\n Breadth first search is not possible”); getch(); } |
سخن پایانی
الگوریتم جستجوی اول سطح (BFS) یک تکنیک پیمایش گراف هست که تمامی رئوس یک گراف رو با ترتیب مشخص، بازدید می‌کنه. توی الگوریتم BFS، ابتدا یک گره مبدأ انتخاب می‌شه و تمامی گره‌های مجاور اون قبل از بررسی گره‌های دیگه، پیماش و بازدید می‌شن. این الگوریتم کاربردهای واقعی متعددی در حوزه‌های مختلف مثل شبکه‌های همتا به همتا، کراولرهای وب، جمع‌آوری زباله و خیلی از حوزه‌های دیگه داره. امیدواریم این مطلب از بلاگ آموزشگاه مهندسی کندو برای شما مفید بوده باشد.
