البحث بالعمق DFS (Depth-First Search)

الصياغة

def dfs(graph, node, visited):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

📄 مثال

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited:
                stack.append(neighbor)
    return order

graph = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(dfs_iterative(graph, "A"))  # ['A', 'B', 'D', 'C']

أهم النقاط

💡 نصائح عملية

• النسخة التعاودية أبسط بالكتابة، لكن النسخة التكرارية (بمكدّس صريح) أأمن مع رسوم بيانية كبيرة جدًا لتفادي تجاوز حد مكدّس الاستدعاءات (stack overflow)

⚠️ أخطاء شائعة

• استخدام DFS لإيجاد أقصر مسار بعدد القفزات — لا تضمن ذلك أبدًا (بعكس BFS)، قد تجد أي مسار صالح وليس الأقصر

خصائص ذات صلة