This guide explains Breadth-First Search (BFS) from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Breadth-First Search (BFS) belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
از رأس شروع حرکت میکنیم، اول همه همسایههای نزدیک را میبینیم و بعد سراغ سطح بعدی میرویم.
Step-by-step process
- رأس شروع را وارد Queue و visited میکنیم.
- اولین رأس Queue را برمیداریم.
- همسایههای دیدهنشده را وارد Queue میکنیم.
- تا خالی شدن Queue یا رسیدن به هدف ادامه میدهیم.
JavaScript example
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;
}Real-world and workplace examples
- کمترین تعداد ارتباط بین دو کاربر شبکه اجتماعی
- کوتاهترین مسیر در Maze یا Grid بدون وزن
- Web Crawler لایهای
- پیدا کردن نزدیکترین Node قابل دسترس
Time and space complexity
O(V + E) time و O(V) space
When should you use it?
Use it when the problem matches this condition: گراف بدون وزن یا یالهای همهزینه.
When is it not a good fit?
It is usually not the best choice when: برای وزنهای متفاوت مناسب نیست..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.