پیمایش عرضی (BFS)
پیمایش عرض اول با صف: بازدید سطح به سطح، پیدا کردن کوتاه‌ترین مسیر در گراف بدون وزن و کاربردها
BFS چیست؟
پیمایش عرض اول (Breadth-First Search) گراف را سطح به سطح پیمایش می‌کند: اول همه همسایه‌های رأس شروع، بعد همسایه‌های همسایه‌ها و... — درست مثل موجی که در آب پخش می‌شود.
ابزار کلیدی: صف
BFS از صف (FIFO) استفاده می‌کند:
- رأس شروع را در صف بگذار و «دیده‌شده» علامت بزن
- رأس جلوی صف را بردار و پردازش کن
- همه همسایه‌های دیده‌نشده را به صف اضافه و علامت بزن
- تکرار تا خالی‌شدن صف
علامت‌گذاری حیاتی است — وگرنه در گراف دارای دور، بی‌نهایت می‌چرخیم!
مثال گام‌به‌گام
گراف: A - B - D
| |
C - E - F
BFS از A:
صف: [A] بازدید: A
صف: [B, C] بازدید: B
صف: [C, D] بازدید: C
صف: [D, E] بازدید: D
صف: [E, F] بازدید: E
صف: [F] بازدید: F
ترتیب: A, B, C, D, E, F (سطح به سطح)قدرت ویژه: کوتاه‌ترین مسیر (بدون وزن)
در گراف بدون وزن، BFS همیشه کوتاه‌ترین مسیر (کمترین تعداد یال) را پیدا می‌کند! چون سطح به سطح پیش می‌رود، اولین باری که به هدف می‌رسد، از کوتاه‌ترین راه آمده است.
برای پیدا کردن خود مسیر، والد هر رأس را ذخیره می‌کنیم و در پایان از هدف به عقب می‌رویم.
پیچیدگی
| معیار | پیچیدگی |
|---|---|
| زمان (لیست همسایگی) | O(V + E) ✓ |
| حافظه | O(V) — صف + مجموعه دیده‌شده |
کاربردهای واقعی
- شبکه‌های اجتماعی: «افرادی که شاید بشناسید» — دوستِ دوست‌ها
- مسیریابی بدون وزن: کمترین تعداد تغییر خط مترو
- خزنده وب: خزیدن سطح به سطح سایت‌ها
- سیستم فایل: پیدا کردن فایل با کمترین عمق
- هوش مصنوعی بازی‌ها: کمترین حرکت تا هدف
- پیدا کردن اجزای همبند گراف
نکته: BFS = صف، DFS = پشته/بازگشت. اگر کوتاه‌ترین مسیر بدون وزن می‌خواهید حتماً BFS؛ DFS ممکن است مسیر طولانی‌تر پیدا کند.
جمع‌بندی
- پیمایش موجی سطح به سطح با صف
- علامت‌گذاری رأس‌ها برای جلوگیری از دور بی‌نهایت
- کوتاه‌ترین مسیر در گراف بدون وزن — کاربرد کلیدی
- O(V + E) با لیست همسایگی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.