البحث بالعرض BFS (Breadth-First Search)

الصياغة

from collections import deque
queue = deque([start])
visited = {start}
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

📄 مثال

from collections import deque

def bfs_shortest_path(graph, start, target):
    visited = {start}
    queue = deque([(start, [start])])
    while queue:
        node, path = queue.popleft()
        if node == target:
            return path
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    return None

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

أهم النقاط

💡 نصائح عملية

• استخدم BFS كلما احتجت أقصر مسار بعدد القفزات برسم غير موزون — أبسط وأسرع إعدادًا من Dijkstra لهذه الحالة تحديدًا

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

• نسيان تسجيل العقدة في visited فور إضافتها للطابور (لا عند إخراجها) — يسبب إضافتها للطابور عدة مرات ويُبطئ الخوارزمية

خصائص ذات صلة