خوارزميات الرسم البياني — BFS و DFS بالصور

شبكة صداقات:
        ┌───┐
   ┌────│أحمد│────┐
   │    └───┘    │
   ▼             ▼
 ┌───┐         ┌───┐
 │سارة│         │خالد│
 └───┘         └───┘
   │             │
   ▼             ▼
 ┌───┐         ┌───┐
 │نور│         │ليلى│
 └───┘         └───┘

graph = {
    "أحمد": ["سارة", "خالد"],
    "سارة": ["أحمد", "نور"],
    "خالد": ["أحمد", "ليلى"],
    "نور": ["سارة"],
    "ليلى": ["خالد"]
}

BFS من "أحمد":

الخطوة 1:        الخطوة 2:         الخطوة 3:
Queue          Queue              Queue
┌───────┐      ┌───────┐          ┌───────┐
│ أحمد  │←OUT  │ سارة  │←OUT      │ نور   │←OUT
├───────┤      ├───────┤          ├───────┤
│       │      │ خالد  │          │ ليلى  │
└───────┘      └───────┘          └───────┘

الترتيب النهائي: أحمد → سارة → خالد → نور → ليلى

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)

    while queue:
        node = queue.popleft()
        print(node, end=" → ")

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS يجد أقصر طريق في شبكة غير موزونة:

أحمد → خالد: خطوتين
أحمد → ليلى: 3 خطوات (أحمد → خالد → ليلى)

DFS من "أحمد" — كأنك تستكشف متاهة:

    أحمد
    │
    ├──→ سارة
    │      │
    │      └──→ نور
    │
    └──→ خالد
           │
           └──→ ليلى

الترتيب: أحمد → سارة → نور → خالد → ليلى

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start, end=" → ")

    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

DFS مع مكدس صريح:

Stack
┌───────┐
│ أحمد  │←POP → نزور أحمد
├───────┤
│ سارة  │←PUSH (جيران أحمد)
│ خالد  │
└───────┘

┌───────┐
│ سارة  │←POP → نزور سارة
├───────┤
│ خالد  │
│ نور   │←PUSH (جيران سارة)
└───────┘

┌───────┐
│ نور   │←POP → نزور نور
├───────┤
│ خالد  │←POP → نزور خالد
└───────┘

┌───────┐
│ ليلى  │←POP → نزور ليلى
└───────┘

BFS (موجة):                      DFS (حفر):
                                 
   ○ ← ○ ← ○                     ○ — ○ — ○
   ↓         ↑                   ╲       ╱
   ○ → ○ → ○                     ○ — ○ — ○
                                 
انتشار كالموجة                  حفر كالنفق
ذاكرة: O(width)                 ذاكرة: O(depth)
أقصر طريق: نعم                  أقصر طريق: لا

المتاهة:
S = البداية, E = النهاية, # = جدار, . = مسار

S  .  .  #  .  .  .
#  #  .  #  .  #  .
.  .  .  .  .  #  .
#  #  #  #  .  #  .
.  .  .  .  .  .  E

BFS يجد أقصر مسار (عدد الخطوات):
S → . → . → # → . → . → .
# → # → . → # → . → # → .
. → . → . → . → . → # → .
# → # → # → # → . → # → .
. → . → . → . → . → . → E

المسار الأمثل: 14 خطوة

شبكة الويب العالمية كرسم بياني:
        ┌───────────┐
        │ google.com │
        └─────┬─────┘
              │
    ┌─────────┼─────────┐
    ▼         ▼         ▼
┌───────┐ ┌───────┐ ┌───────┐
│  github│ │stack  │ │youtube│
│  .com  │ │overflow│ │ .com  │
└───────┘ └───────┘ └───────┘
    │         │         │
    ▼         ▼         ▼
┌───────┐ ┌───────┐ ┌───────┐
│  more  │ │  more │ │  more │
│ links  │ │ links │ │ links │
└───────┘ └───────┘ └───────┘

BFS → crawl بالعرض (صفحات قريبة أولاً)
DFS → crawl بعمق (مسار كامل قبل الانتقال)