الگوریتم BFS چیست؟ – به زبان ساده + مثال

یکی از موضوعات مهم در مباحث طراحی الگوریتم و برنامه نویسی، روش‌های جستجو در «ساختمان داده‌‌های» (Data Structures) مختلف است. به عبارتی، از الگوریتم‌های جستجو به منظور بازیابی مقادیر خاصی از اطلاعات ذخیره شده در ساختار داده‌های مختلف استفاده می‌شود. الگوریتم «جستجوی اول سطح» (Breadth First Search | BFS) به عنوان یکی از الگوریتم‌های جستجوی رایج برای «گراف» (Graph) و «درخت» (Tree) محسوب می‌شود. در این مطلب از مجله فرادرس قصد داریم به این پرسش پاسخ دهیم که ویژگی‌ها و مزایا و معایب الگوریتم BFS چیست و با ارائه یک مثال ساده، به توضیح مرحله به مرحله این الگوریتم برای پیدا کردن پاسخ مسئله می‌پردازیم.

الگوریتم های پیمایش ساختار داده ها

الگوریتم‌های پیمایش، روشی برای جستجوی یک گره در ساختمان داده‌های درخت و گراف به حساب می‌آیند. درخت و گراف به عنوان ۲ ساختار داده در طراحی الگوریتم و برنامه نویسی محسوب می‌شوند که از آن‌ها می‌توان برای نمایش و نگهداری داده‌ها به نحوی استفاده کرد که ارتباطی بین آن‌ها وجود داشته باشد. این نوع ارتباط در ساختار داده درخت می‌تواند به صورت سلسله‌مراتبی و بدون وجود حلقه باشد و در گراف می‌توان ارتباطی را بین داده‌ها ایجاد کرد که باعث شکل‌گیری حلقه در گراف شود.

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم در فرادرس

کلیک کنید

به منظور یافتن مقداری خاص در این ۲ نوع ساختار داده، می‌توان از ۲ روال جستجو استفاده کرد:

• روش «جستجوی اول سطح» (Breadth-First Search) یا همان الگوریتم BFS
• روش «جستجوی اول عمق» (Depth-First Search) یا الگوریتم DFS

در مطلب حاضر، قصد داریم به روش جستجوی اول سطح بپردازیم و با مثال کاربردی مراحل آن را توضیح دهیم.

الگوریتم BFS چیست ؟

الگوریتم BFS برای جستجوی مقداری خاص در یک درخت یا گراف استفاده می‌شود. روال جستجوی الگوریتم BFS از گره ریشه درخت یا گراف آغاز می‌شود. در هر سطح از درخت یا گراف، تمامی گره‌ها مورد بررسی قرار می‌گیرند و سپس روند جستجو در سطح بعدی این ساختار داده‌ها ادامه پیدا می‌کند. با کمک این الگوریتم می‌توان بدون گیر افتادن در یک حلقه بی‌پایان، هر گره را بررسی کرد.

فیلم آموزش نظریه گراف و کاربردها در فرادرس

کلیک کنید

الگوریتم جستجوی اول سطح از ساختار داده «صف» (Queue) برای پیمایش گراف یا درخت استفاده می‌کند. یکی از اصول ساختار داده صف، اصل «اولین ورودی - اولین خروجی» (First In - First Out | FIFO) است. الگوریتم BFS با استفاده از چنین اصلی، در هر گامی که گره جدیدی را در گراف یا درخت ملاحظه می‌کند،‌ گره‌های مجاور (گره‌های فرزند) آن را در صف قرار می‌دهد و سپس گره‌های موجود در صف را با اصل FIFO برای یافتن پاسخ،‌ بررسی می‌کند. به منظور درک بهتر عملکرد این الگوریتم، در بخش‌های بعدی این مطلب، مثالی کاربردی ارائه کرده‌ایم.

کاربرد الگوریتم جستجوی اول سطح

الگوریتم BFS به عنوان یکی از الگوریتم‌های ساده جستجو محسوب می‌شود و می‌توان به سادگی آن را با استفاده از زبان برنامه نویسی پیاده‌سازی کرد، از این الگوریتم در مسائل مختلف مهمی استفاده می‌شود که در ادامه به برخی از آن‌ها اشاره شده است:

فیلم آموزش ساختمان داده ها – مرور و تست کنکور ارشد در فرادرس

کلیک کنید

• کاربرد الگوریتم BFS در پیدا کردن کوتاه‌ترین مسیر پاسخ در گراف غیر وزن‌دار: از آنجایی که الگوریتم BFS سطر به سطر سطح یک درخت را پیمایش می‌کند، این تضمین وجود دارد که کوتاه‌ترین مسیر برای پیدا کردن گره مورد نظر طی شده است.
• کاربرد الگوریتم جستجوی اول سطح در شبکه‌های نظیر به نظیر «Peer To Peer Networks»: در چنین شبکه‌هایی مانند شبکه BitTorrent از این الگوریتم به منظور پیدا کردن گره‌های همسایه استفاده می‌شود.
• استفاده از الگوریتم BFS در موتورهای جستجو: «خزشگر» (Crawler) وب از این الگوریتم برای استخراج اطلاعات از صفحات اینترنت استفاده می‌کند. خزشگرها با کمک این روش، از یک صفحه اینترنتی، کار استخراج اطلاعات را شروع می‌کنند و با استفاده از لینک‌های موجود در صفحه اینترنت، روند جستجوی خود را در صفحات لینک داده شده، ادامه می‌دهند.
• استفاده از الگوریتم جستجوی اول سطح در شبکه‌های اجتماعی: یافتن افراد مختلف در شبکه‌های اجتماعی بر اساس این الگوریتم انجام می‌شود. برای مثال، این الگوریتم افرادی را که با دوستان شما لینک هستند، به شما پیشنهاد می‌دهند تا اگر آن‌ها را می‌شناسید، با آن‌ها ارتباط برقرار کنید.
• کاربرد الگوریتم BFS در شبکه: از این الگوریتم می‌توان برای انتشار بسته در طول یک شبکه استفاده کرد تا بسته ارسالی به تمامی گره‌ها برسد.
• تشخیص وجود حلقه در گراف‌های جهت‌دار و غیر جهت‌دار با استفاده از الگوریتم جستجوی اول سطح
• بررسی تمامی گره‌ها: با استفاده از الگوریتم جستجوی اول سطح می‌توان تمام گره‌هایی را درون گراف یا درخت پیدا کرد که از گره آغازین می‌توان به آن‌ها دسترسی داشت.

تفاوت پیمایش الگوریتم BFS در گراف و درخت چیست ؟

همان‌طور که گفتیم، از الگوریتم جستجوی اول سطح به منظور پیمایش درخت یا گراف برای یافتن مقداری خاص استفاده می‌شود. روال پیمایش الگوریتم BFS در گراف، مشابه با روال جستجوی این الگوریتم در ساختار داده درخت است. تنها نکته‌ای که باید به آن توجه کنیم، این است که گراف می‌تواند شامل حلقه باشد. به همین خاطر، در روال جستجو ممکن است با یک گره بیش از یک بار برخورد کنیم.

فیلم آموزش مبانی برنامه نویسی – الگوریتم و فلوچارت با رویکرد حل مساله در فرادرس

کلیک کنید

به منظور جلوگیری از بازدید یک گره بیش از یک بار، می‌توان دو دسته مجزا برای راس‌های گراف در نظر بگیریم:

• راس‌های دیده شده
• راس‌های دیده نشده

برای استفاده از الگوریتم جستجوی اول سطح در پیمایش درخت،‌ چنین شرطی لحاظ نمی‌شود، زیرا ساختار درخت به نحوی است که حلقه در آن ایجاد نمی‌شود. در ادامه مطلب، به مراحل الگوریتم BFS‌ می‌پردازیم و مثال واضحی برای آن ارائه خواهیم کرد.

مراحل الگوریتم جستجوی اول سطح چیست ؟

مراحل پیمایش گراف یا درخت را با استفاده از الگوریتم BFS می‌توان در چندین مرحله خلاصه کرد. در ادامه،‌ به توضیح این مراحل می‌پردازیم:

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

1. گام اول: گرافی را تعریف کنید که قصد پیمایش آن را با استفاده از الگوریتم BFS‌ دارید.
2. گام دوم: راس نخست گراف را انتخاب کنید. پیمایش گراف، از این راس آغاز می‌شود.
3. گام سوم: می‌توان از ساختار داده‌های «آرایه» (Array) و صف برای پیمایش گراف استفاده کرد. آرایه تعریف شده، برای نگهداری راس‌هایی از گراف هستند که با پیمایش گراف، ملاحظه شده‌اند.
4. گام چهارم: راس اول را به آرایه اضافه کنید. سپس، راس‌های مجاور راس نخست را به ساختار داده صف اضافه کنید.
5. گام پنجم: از روش «اولین ورودی - اولین خروجی» (First In - First Out | FIFO) برای حذف اولین آیتم موجود در صف استفاده کنید. آیتم خارج شده از صف را درون آرایه قرار دهید و سپس راس‌های مجاور آیتم حذف شده را به صف اضافه کنید.
6. گام ششم: گام پنجم را آنقدر تکرار کنید تا راسی از گراف باقی نماند.

مثال کاربردی از الگوریتم BFS

در این بخش قصد داریم مثالی ساده برای درک بهتر از عملکر الگوریتم جستجوی BFS ارائه کنیم. بدین منظور، در مرحله اول، گرافی را برای پیمایش تعیین می‌کنیم که در ادامه آن را ملاحظه می‌کنید.

در مرحله دوم، ۲ ساختار داده خالی آرایه و صف ایجاد می‌کنیم.

در مرحله سوم، گره اول گراف را درون صف قرار می‌دهیم و این گره را به عنوان گره ملاحظه شده درون آرایه ذخیره می‌کنیم.

گره ملاحظه شده را از ابتدای صف حذف می‌کنیم و گره‌های مجاور گره حذف شده از صف را درون صف و آرایه قرار می‌دهیم.

گره ۱ را از ابتدای صف حذف و گره مجاور آن را به صف و آرایه اضافه می‌کنیم.

سپس، گره ۲ را از ابتدای صف حذف کرده و گره مجاور آن را به صف و آرایه اضافه می‌کنیم.

گره ۳ را از صف حذف می‌کنیم و اگر گره ۳ دارای گره مجاوری باشد که از قبل، آن گره ملاحظه نشده باشد، آن را به صف و آرایه اضافه می‌کنیم. از آنجایی که گره ۴ به عنوان گره مجاور گره ۳ است و در مراحل قبل، گره ۴ به آرایه اضافه شده بود، مجدداً آن را به آرایه اضافه نمی‌کنیم. بدین‌ترتیب، گره بعدی موجود در صف را حذف می‌کنیم.

پس از حذف گره ۴ از صف، بررسی می‌کنیم آیا گره مجاور جدیدی برای گره ۴ وجود دارد؟ همان‌طور که در تصویر زیر ملاحظه می‌کنید، گره مجاور جدیدی برای گره ۴ موجود نیست و تمامی گره‌های گراف با استفاده از الگوریتم BFS پیمایش شدند. در صورتی که گره‌ای از گراف باقی نمانده باشد، صف مقدارش خالی می‌شود و در این حالت، کار پیمایش الگوریتم BFS‌ به اتمام می‌رسد.

پیچیدگی زمانی و پیچیدگی فضایی الگوریتم جستجوی BFS چیست؟