تستخدم BFS طابوراً Queue لاستكشاف الرسم البياني حسب المسافة من نقطة البداية: المستوى الأول ثم الثاني ثم الثالث.
أهم ميزة لها هي إيجاد أقصر مسار بعدد الحواف في الرسم غير الموزون أو عندما تكون جميع الحواف متساوية التكلفة.
الفكرة الأساسية
FIFO — First In, First Outنحدد العقدة كـ visited عند إدخالها إلى Queue حتى لا تدخل أكثر من مرة.
JavaScript
function bfs(graph, start) {
const queue = [start];
let head = 0;
const visited = new Set([start]);
const order = [];
while (head < queue.length) {
const current = queue[head++];
order.push(current);
for (const next of graph[current] ?? []) {
if (visited.has(next)) continue;
visited.add(next);
queue.push(next);
}
}
return order;
}أقصر مسار
لأن BFS تزور العقد بترتيب عدد الحواف، فإن أول وصول إلى عقدة يمثل أقل عدد من الحواف إليها.
يمكن حفظ distance و parent لإعادة بناء المسار.
BFS و DFS
BFS تتحرك مستوى بعد مستوى باستخدام Queue، بينما DFS تتعمق باستخدام Stack أو recursion.
BFS تضمن أقصر مسار في الرسم غير الموزون؛ DFS لا تضمن ذلك.
Grid و Maze
كل Cell يمكن اعتباره Vertex وكل حركة Edge. إذا كانت الحركات متساوية التكلفة، فإن BFS تجد أقل عدد من الحركات.
Multi-Source BFS
يمكن وضع عدة مصادر في Queue بمسافة صفر. تستخدم في أقرب مستشفى، انتشار النار، العدوى وأقرب مخرج.
Bidirectional BFS
عند معرفة البداية والهدف يمكن البحث من الطرفين لتقليل مساحة البحث.
0-1 BFS
إذا كانت الأوزان فقط 0 و1، يمكن استخدام Deque بدلاً من BFS العادية.
التطبيقات
- Social Networks
- Maze و Grid
- Web Crawling
- Connected Components
- Bipartite Check
- Minimum Moves
- State Search
التعقيد
Time: O(V + E)
Space: O(V)الخلاصة
إذا كان المطلوب أقرب حالة أو أقل عدد من الخطوات في Graph غير موزون، فـ BFS غالباً هي الاختيار الصحيح.