الگوریتم جستجوی سطح اول (Breadth-First Search - BFS) یکی از مهم‌ترین الگوها برای حل مسائل مرتبط با ساختارهای داده غیرخطی مانند درخت‌ها و گراف‌ها است.
در زیر توضیحی عمیق درباره این الگوریتم ارائه شده است:
۱. هدف و مکانیسم BFS
BFS الگوریتمی است که برای پیمایش گره‌ها در یک گراف یا درخت به صورت سطح به سطح (level by level) استفاده می‌شود.
- روش پیمایش: این الگوریتم از یک گره مشخص، که معمولاً ریشه (root) نامیده می‌شود، شروع می‌کند.
- اولویت: ابتدا، الگوریتم تمام همسایگان مستقیم گره ریشه را کاوش می‌کند، قبل از اینکه به سراغ همسایگانِ همسایگان (سطح بعدی) و به همین ترتیب، پیش برود.
۲. ساختار داده اصلی: صف (Queue)
BFS برای پیگیری گره‌هایی که باید کاوش شوند و برای حفظ نظم صحیح پیمایش، از یک صف (Queue) استفاده می‌کند.
- اصل FIFO: صف یک ساختار داده است که بر اساس اصل “اولین ورودی، اولین خروجی” (First In, First Out - FIFO) کار می‌کند.
- تضمین ترتیب: استفاده از صف تضمین می‌کند که گره‌ها به ترتیب صحیح بازدید می‌شوند؛ یعنی از نزدیک‌ترین گره به ریشه شروع کرده و به سمت بیرون حرکت می‌کنند.
۳. کاربردهای BFS
BFS یک الگوریتم متداول است و برای حل مسائلی که نیاز به کاوش لایه به لایه دارند، ایده‌آل است. مهم‌ترین کاربرد آن یافتن کوتاه‌ترین مسیر (Shortest Path) در یک گراف غیروزن‌دار است.
۴. BFS در عمل: پیمایش سطح به سطح یک درخت دودویی
یک مسئله متداول که با استفاده از BFS حل می‌شود، پیمایش سطح به سطح یک درخت دودویی (Level Order Traversal) است. این مسئله از ما می‌خواهد که تمام سطوح درخت را در هر عمق ارائه دهیم.
برای حل این مسئله با BFS، مراحل زیر دنبال می‌شوند:
- شروع: ابتدا گره ریشه (Root Node) را به صف اضافه می‌کنیم.
- پردازش سطح: برای هر سطح، تمام گره‌هایی که در حال حاضر در صف قرار دارند، پردازش می‌شوند.
- افزودن مقادیر: گره پردازش‌شده از صف حذف شده و مقدار آن به نتیجه اضافه می‌شود.
- حرکت به سطح بعدی: برای هر گره‌ای که پردازش می‌شود، فرزندان چپ و راست آن (در صورت وجود) به صف اضافه می‌شوند تا در سطح بعدی پردازش شوند.
- تکرار: این فرآیند آنقدر تکرار می‌شود تا صف خالی شود.
این تضمین می‌کند که همه گره‌های یک سطح قبل از حرکت به سطح بعدی بازدید شوند. به عنوان مثال، اگر درختی با ریشه ۳ و فرزندان ۹ و ۲۰ داشته باشیم (که ۲۰ دارای فرزندان ۱۵ و ۷ است)، مقادیر گره‌ها به ترتیب زیر برگردانده می‌شوند: ابتدا ۳، سپس ۹ و ۲۰، و در نهایت ۱۵ و ۷.
۵. BFS در مقایسه با DFS
BFS یکی از دو الگوریتم اصلی برای مسائل غیرخطی است، در حالی که الگوریتم دیگر جستجوی عمق اول (DFS) است.
| ویژگی | BFS (جستجوی سطح اول) | DFS (جستجوی عمق اول) |
|---|---|---|
| ساختار داده | صف (Queue) | پشته (Stack) یا پشته تماس بازگشتی |
| روش کاوش | سطح به سطح (Level by Level) | عمیق شدن تا انتها (Dive Deep) |
| کاربرد اصلی | یافتن کوتاه‌ترین مسیر، پیمایش لایه‌ای | کاوش تمام مسیرها، تشخیص چرخه‌ها، بررسی تمام پیکربندی‌ها |
توجه: اگر یک گراف ممکن است شامل چرخه باشد، مانند یک گراف معمولی (در مقابل یک درخت که چرخه ندارد)، برای BFS نیاز به یک مجموعه بازدید شده (visited set) دارید تا گره‌هایی را که قبلاً پیمایش کرده‌اید، پیگیری کنید تا از حلقه‌های نامحدود جلوگیری شود.