ما هي خوارزمية البحث بالعرض أولاً (BFS)؟

Question

Accepted Answer

**BFS** تستكشف رسم بياني مستوى تلو الآخر، وتزور جميع الجيران قبل الانتقال إلى أعمق. وتستخدم **queue** وتجد **أقصر مسار** (أقل عدد حواف) في الرسوم البيانية غير الموزونة.

## الفكرة

ابدأ من مصدر، أدرجها في queue، ثم كرر إزالة عقدة من queue، قم بزيارة جيرانها غير المزارين، وأدرجهم في queue. مجموعة `visited` تمنع إعادة الزيارة.

## مثال

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## التعقيد

- **الوقت:** O(V + E) — كل vertex وحافة مرة واحدة.
- **المساحة:** O(V) لـ queue ومجموعة visited.

## متى تستخدم / الأخطاء الشائعة

استخدم BFS لـ **أقصر مسار في الرسوم البيانية غير الموزونة**، traversal على مستوى المستويات، وإيجاد المكونات المترابطة. تستخدم ذاكرة أكثر من DFS (حدود كاملة في المرة الواحدة). تتبع `visited` دائماً أو قد تدخل في حلقة لا نهائية على الدورات.

## لماذا يهم

BFS هي *الخوارزمية* لأقصر المسارات عندما تحسب كل حافة بالتساوي — التوجيه، زحف الويب، درجات الانفصال في الشبكات الاجتماعية.

هيكلها القائم على queue والمستوى تلو الآخر هو نمط traversal أساسي.

معرفة BFS مقابل DFS تسمح لك باختيار الأداة المناسبة لمشاكل القابلية للوصول والمسارات والترتيب.