BFS گراف را سطحبهسطح با Queue میپیماید و برای کوتاهترین مسیر در گراف بدون وزن بسیار مهم است. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Breadth-First Search (BFS) زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
از رأس شروع حرکت میکنیم، اول همه همسایههای نزدیک را میبینیم و بعد سراغ سطح بعدی میرویم.
مراحل اجرا
- رأس شروع را وارد Queue و visited میکنیم.
- اولین رأس Queue را برمیداریم.
- همسایههای دیدهنشده را وارد Queue میکنیم.
- تا خالی شدن Queue یا رسیدن به هدف ادامه میدهیم.
نمونه کد JavaScript
function bfs(graph, start) {
const q = [start], seen = new Set([start]), order = [];
while (q.length) {
const u = q.shift(); order.push(u);
for (const v of graph[u] ?? []) if (!seen.has(v)) {
seen.add(v); q.push(v);
}
}
return order;
}مثالهای واقعی و دنیای کار
- کمترین تعداد ارتباط بین دو کاربر شبکه اجتماعی
- کوتاهترین مسیر در Maze یا Grid بدون وزن
- Web Crawler لایهای
- پیدا کردن نزدیکترین Node قابل دسترس
پیچیدگی زمانی و فضایی
O(V + E) زمان و O(V) حافظه
چه زمانی استفاده کنیم؟
گراف بدون وزن یا یالهای همهزینه
چه زمانی مناسب نیست؟
برای وزنهای متفاوت مناسب نیست.
جمعبندی
Breadth-First Search (BFS) را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.