ما هو البحث بالعمق أولاً (DFS)؟

Question

Accepted Answer

**DFS** يستكشف الرسم البياني بالذهاب بأعمق ما يمكن على طول كل فرع قبل العودة للخلف. يستخدم **مكدس** (غالباً مكدس الاستدعاء عبر التكرار العودي) ويزور المسار الكامل قبل استكشاف البدائل.

## الفكرة

من عقدة، قم بالتكرار العودي إلى جار غير مزار، واستمر بالذهاب بعمق؛ عند الوقوع في طريق مسدود، عد للخلف وجرب فرعاً آخر.

## مثال

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

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

## BFS مقابل DFS

| | BFS | DFS |
|---|-----|-----|
| البنية | طابور | مكدس / تكرار عودي |
| يجد | الأقصر (بدون أوزان) | أي مسار |
| الذاكرة | O(V) الحد الأمامي | O(العمق) |
| مناسب ل | أقصر المسارات، المستويات | الدورات، الترتيب الطوبولوجي، المكونات |

## التعقيد

- **الوقت:** O(V + E). **المساحة:** O(V) (عمق التكرار العودي + المزار).

## الأخطاء الشائعة

الرسوم البيانية العميقة قد تتجاوز مكدس التكرار العودي — استخدم مكدساً صريحاً. تتبع `visited` للتعامل مع الدورات.

## لماذا يهم

DFS يشكل أساس كشف الدورات والترتيب الطوبولوجي والمكونات المتصلة وتوليد المتاهات والمسارات.

أناقته العودية تجعل كود الأشجار والرسوم البيانية موجزاً.

معرفة متى يتفوق البحث بالعمق أولاً على البحث بالعرض أولاً هي أساس الإلمام بخوارزميات الرسوم البيانية.

	BFS	DFS
البنية	طابور	مكدس / تكرار عودي
يجد	الأقصر (بدون أوزان)	أي مسار
الذاكرة	O(V) الحد الأمامي	O(العمق)
مناسب ل	أقصر المسارات، المستويات	الدورات، الترتيب الطوبولوجي، المكونات