تخطَّ إلى المحتوى

🧮 شرح هياكل البيانات والخوارزميات

اجتياز الرسوم: BFS و DFS

الدرس 16 من 25· ⏱ 1 دقائق قراءة

البحث بالعمق (DFS)

يتعمّق في فرع حتى نهايته قبل التراجع — يستخدم مكدّسًا (أو التعاوديّة).

def dfs(graph, node, visited=set()):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbor in graph[node]:
        dfs(graph, neighbor, visited)

البحث بالعرض (BFS)

يزور كل الجيران في مستوى قبل الانتقال للأعمق — يستخدم طابورًا.

from collections import deque
def bfs(graph, start):
    visited = {start}
    q = deque([start])
    while q:
        node = q.popleft()
        print(node)
        for n in graph[node]:
            if n not in visited:
                visited.add(n)
                q.append(n)

متى نستخدم أيًّا؟

  • BFS: أقصر مسار في رسم غير موزون، أقرب العقد.
  • DFS: استكشاف كل المسارات، كشف الدورات، الترتيب الطوبولوجي.

التعقيد لكليهما: O(V + E).

🎯 التالي: خوارزميات الترتيب الأساسية.

هل كان هذا الدرس مفيدًا؟