# فصل ۰۶ — `BFS` و `DFS`: کدام چه چیزی پیدا می‌کند

<div dir="rtl">

# فصل ۰۶ — `BFS` و `DFS`: کدام چه چیزی پیدا می‌کند

## در این فصل چه یاد می‌گیری

دو پیمایشِ فصلِ ۲ را روی گراف می‌بریم. کد تقریباً همان است — یکی `queue` دارد و دیگری `stack` — ولی **این بار تفاوتشان تزئینی نیست:** یکی کوتاه‌ترین مسیر را می‌دهد و دیگری نمی‌دهد.

روی یک گرافِ هشت‌گره‌ای، `BFS` مسیرِ یک‌یالی پیدا می‌کند و `DFS` مسیرِ شش‌یالی — **هر دو معتبر، فقط یکی‌شان جوابِ سؤال است.** بعد یک کد می‌بینی که با عوض شدنِ **یک کلمه** به‌جای فاصله‌های `[0, 1, 3, 2, 3, 3, 2, 1]` جوابِ `[0, 1, 6, 5, 4, 3, 2, 1]` می‌دهد، هر هشت گره را هم می‌بیند، و هیچ خطایی نمی‌دهد.

آخرش هم `O(V+E)` را می‌سنجیم — با شمارنده‌ای که **دقیقاً** `V + 2E` درمی‌آید.

![دو موجِ متفاوت که از یک گرهِ واحد در یک شبکه پخش می‌شوند: یکی حلقه‌های هم‌مرکز و دیگری یک رشتهٔ باریکِ عمیق](/lesson-assets/t5-s06-bfs-dfs/prompt/01-image-two-frontiers.png)

آخر این فصل می‌توانی:

- `BFS` و `DFS` را روی گراف بنویسی و ترتیبِ بازدیدشان را توضیح بدهی
- **کوتاه‌ترین مسیر در گرافِ بی‌وزن را فقط با `BFS` بگیری** و بگویی چرا `DFS` این کار را نمی‌کند
- نقشِ مجموعهٔ دیده‌شده‌ها را نشان بدهی — با خطایی که بدونِ آن می‌گیری
- `O(V+E)` را با شمارنده تأیید کنی، در هر دو محور

## قبل از شروع

**از فصلِ ۵:** فهرستِ مجاورت، و اینکه فهرستِ همسایه‌ها را مرتب نگه می‌داریم تا نتیجه تکرارپذیر بماند. **از فصلِ ۲:** `stack` و `queue` روی درخت، و اینکه ترتیبِ `push` جوابِ نهایی را عوض می‌کند.

**یک تفاوتِ مهم با درخت:** گراف حلقه دارد. در درخت هیچ‌وقت به گره‌ای که دیده‌ای برنمی‌گشتی، این‌جا برمی‌گردی — **و کلِ فرقِ کدِ این فصل با فصلِ ۲ همان مجموعهٔ دیده‌شده‌هاست.**

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | کمتر از یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-5-trees-and-graphs/session-06-bfs-dfs.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. یک گرافِ کوچک، با یک میان‌بُر

هشت گره و هشت یال. **گرهٔ `0` هم به `1` وصل است و هم مستقیم به `7`** — و بقیهٔ گراف یک راهِ طولانیِ دیگر از `0` به `7` می‌سازد. این میان‌بُر تمامِ نکتهٔ فصل است.

</div>

```python
from collections import deque

EDGES = [(0, 1), (0, 7), (1, 3), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7)]
small = {node: [] for node in range(8)}
for a, b in EDGES:
    small[a].append(b)
    small[b].append(a)
for node in small:
    small[node].sort()          # ترتیبِ ثابت، تا هر اجرا همان جواب را بدهد

for node in sorted(small):
    print(f"گرهٔ {node}: {small[node]}")
```

```text
گرهٔ 0: [1, 7]
گرهٔ 1: [0, 3]
گرهٔ 2: [3]
گرهٔ 3: [1, 2, 4]
گرهٔ 4: [3, 5]
گرهٔ 5: [4, 6]
گرهٔ 6: [5, 7]
گرهٔ 7: [0, 6]
```

<div dir="rtl">

## ۲. دو پیمایش، دو ترتیب

کدِ هر دو یک قالب دارد: **یک ظرفِ انتظار، یک مجموعهٔ دیده‌شده‌ها، و یک حلقه.** تنها تفاوت این است که از کدام سرِ ظرف برمی‌داری.

</div>

```python
def bfs_order(graph, start):
    """با queue: هر چه زودتر دیده شده، زودتر باز می‌شود."""
    seen = {start}
    out = []
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        out.append(node)
        for nbr in graph[node]:
            if nbr not in seen:
                seen.add(nbr)
                waiting.append(nbr)
    return out


def dfs_order(graph, start):
    """با stack: هر چه دیرتر دیده شده، زودتر باز می‌شود."""
    seen = set()
    out = []
    pending = [start]
    while pending:
        node = pending.pop()
        if node in seen:
            continue
        seen.add(node)
        out.append(node)
        for nbr in reversed(graph[node]):
            if nbr not in seen:
                pending.append(nbr)
    return out


print("BFS از گرهٔ ۰:", bfs_order(small, 0))
print("DFS از گرهٔ ۰:", dfs_order(small, 0))
print("هر دو همان گره‌ها را دیده‌اند؟",
      sorted(bfs_order(small, 0)) == sorted(dfs_order(small, 0)))
```

```text
BFS از گرهٔ ۰: [0, 1, 7, 3, 6, 2, 4, 5]
DFS از گرهٔ ۰: [0, 1, 3, 2, 4, 5, 6, 7]
هر دو همان گره‌ها را دیده‌اند؟ True
```

<div dir="rtl">

**`BFS` اول هر دو همسایهٔ مستقیم را دید (`1` و `7`)، بعد رفت سراغِ همسایه‌های آن‌ها.** یعنی سطح به سطح دور می‌شود.

**`DFS` بعد از `1` مستقیم رفت به `3` و تا ته آن شاخه ادامه داد** و آخر از همه به `7` رسید — با اینکه `7` همسایهٔ مستقیمِ نقطهٔ شروع بود.

**همان گره‌ها، ترتیبِ کاملاً متفاوت.** و بخشِ بعد نشان می‌دهد این ترتیب چه چیزی را تعیین می‌کند.

## ۳. کوتاه‌ترین مسیر: فقط یکی از این دو

</div>

```python
def bfs_path(graph, start, goal):
    """کوتاه‌ترین مسیر در گرافِ بی‌وزن — چون BFS سطح به سطح جلو می‌رود."""
    came_from = {start: None}
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        if node == goal:
            break
        for nbr in graph[node]:
            if nbr not in came_from:
                came_from[nbr] = node
                waiting.append(nbr)
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = came_from[node]
    return path[::-1]


def dfs_path(graph, start, goal, seen=None, path=None):
    """اولین مسیری که DFS پیدا می‌کند — نه لزوماً کوتاه‌ترین."""
    if seen is None:
        seen, path = {start}, [start]
    if start == goal:
        return list(path)
    for nbr in graph[start]:
        if nbr not in seen:
            seen.add(nbr)
            path.append(nbr)
            found = dfs_path(graph, nbr, goal, seen, path)
            if found:
                return found
            path.pop()
    return None


bfs_route = bfs_path(small, 0, 7)
dfs_route = dfs_path(small, 0, 7)
print("مسیرِ BFS:", bfs_route, "· طول:", len(bfs_route) - 1, "یال")
print("مسیرِ DFS:", dfs_route, "· طول:", len(dfs_route) - 1, "یال")
print("هر دو مسیرِ معتبرند؟",
      all(b in small[a] for a, b in zip(bfs_route, bfs_route[1:]))
      and all(b in small[a] for a, b in zip(dfs_route, dfs_route[1:])))
```

```text
مسیرِ BFS: [0, 7] · طول: 1 یال
مسیرِ DFS: [0, 1, 3, 4, 5, 6, 7] · طول: 6 یال
هر دو مسیرِ معتبرند؟ True
```

<div dir="rtl">

**یک یال در برابرِ شش یال، و هر دو مسیرِ کاملاً معتبرند.**

`DFS` دروغ نگفته — مسیری که برگردانده واقعاً از `0` به `7` می‌رسد و هر یالش وجود دارد. **فقط جوابِ سؤالِ دیگری است:** «یک مسیر پیدا کن»، نه «کوتاه‌ترین مسیر را پیدا کن».

**و دلیلِ اینکه `BFS` کوتاه‌ترین را می‌دهد، یک جمله است: `BFS` گره‌ها را به‌ترتیبِ فاصله از مبدأ باز می‌کند.** وقتی برای اولین بار به گرهی می‌رسی، از هر راهِ دیگری هم برسی نمی‌تواند کوتاه‌تر باشد، چون همهٔ راه‌های کوتاه‌تر قبلاً بررسی شده‌اند. **این استدلال فقط وقتی کار می‌کند که همهٔ یال‌ها هزینهٔ یکسان داشته باشند** — یعنی گرافِ بی‌وزن. اگر یال‌ها وزن داشته باشند، `BFS` هم دیگر تضمینی نمی‌دهد و به الگوریتمِ دیگری احتیاج داری که موضوعِ این دوره نیست.

**ولی این یک استدلال است، نه یک اندازه‌گیری** — و قاعدهٔ این دوره می‌گوید جوابِ هر نسخه باید با یک جوابِ **مستقلاً درست** با `==` سنجیده شود. کدِ بالا فقط وارسی کرد که هر دو مسیر **معتبرند**، نه اینکه کوتاه‌ترین‌اند.

**پس کوتاه‌ترین را از راهِ کاملاً متفاوتی حساب می‌کنیم: همهٔ مسیرهای ساده را می‌بینیم و کمینه‌شان را برمی‌داریم.** روی این گرافِ هشت‌گره‌ای ارزان است. **فعلاً همین‌قدر بدان که این کار روی گرافِ بزرگ‌تر منفجر می‌شود؛ فصلِ بعد دقیقاً همان است و عددش را می‌دهد.**

</div>

```python
def every_path(graph, node, goal, seen, path, out):
    """همهٔ مسیرهای ساده از node تا goal — گران است و فصلِ بعد می‌گوید چقدر."""
    if node == goal:
        out.append(list(path))
        return
    for nbr in graph[node]:
        if nbr not in seen:
            seen.add(nbr)
            path.append(nbr)
            every_path(graph, nbr, goal, seen, path, out)
            path.pop()
            seen.discard(nbr)


def brute_distance(graph, start, goal):
    """کوتاه‌ترین فاصله، بدونِ هیچ زیرکی: کمینه روی همهٔ مسیرهای ممکن."""
    routes = []
    every_path(graph, start, goal, {start}, [start], routes)
    return min(len(r) for r in routes) - 1


by_bfs = [len(bfs_path(small, 0, g)) - 1 for g in range(8)]
by_brute = [brute_distance(small, 0, g) for g in range(8)]
print("فاصله‌های BFS        :", by_bfs)
print("کمینه روی همهٔ مسیرها:", by_brute)
print("هر هشت گره یکی درآمدند؟", by_bfs == by_brute)
print("و مسیرِ DFS تا گرهٔ ۷:", len(dfs_route) - 1,
      "یال — برابرِ کوتاه‌ترین؟", len(dfs_route) - 1 == by_brute[7])
```

```text
فاصله‌های BFS        : [0, 1, 3, 2, 3, 3, 2, 1]
کمینه روی همهٔ مسیرها: [0, 1, 3, 2, 3, 3, 2, 1]
هر هشت گره یکی درآمدند؟ True
و مسیرِ DFS تا گرهٔ ۷: 6 یال — برابرِ کوتاه‌ترین؟ False
```

<div dir="rtl">

**حالا ادعا اندازه‌گیری شده، نه استدلال‌شده.** برای **هر هشت** گره، فاصله‌ای که `BFS` می‌دهد دقیقاً همان کمینهٔ همهٔ مسیرهای ممکن است — و `DFS` روی یکی از همان هشت‌تا `False` می‌دهد.

**و روشِ کند اینجا فقط یک ابزارِ وارسی است، نه یک نامزد.** روی گرافِ هزارگره‌ایِ بخشِ ۶ هرگز نمی‌شود اجرایش کرد. **ولی روی یک گرافِ هشت‌گره‌ای، همان چیزی است که ادعا را از حرف به نتیجه تبدیل می‌کند** — دقیقاً همان کاری که ترمِ ۴ فصلِ ۶ با مرزِ پایین کرد.

## ۴. تلهٔ بی‌صدا: همان کد، یک کلمه فرق

`BFS` فاصله هم می‌دهد، نه فقط مسیر. حالا همان تابع را با یک تغییرِ کوچک می‌نویسیم: `popleft` را می‌کنیم `pop`.

</div>

```python
def bfs_distances(graph, start):
    dist = {start: 0}
    waiting = deque([start])
    while waiting:
        node = waiting.popleft()
        for nbr in graph[node]:
            if nbr not in dist:
                dist[nbr] = dist[node] + 1
                waiting.append(nbr)
    return dist


def broken_distances(graph, start):
    """همان کد، فقط popleft به pop تبدیل شده."""
    dist = {start: 0}
    waiting = deque([start])
    while waiting:
        node = waiting.pop()
        for nbr in graph[node]:
            if nbr not in dist:
                dist[nbr] = dist[node] + 1
                waiting.append(nbr)
    return dist


right = bfs_distances(small, 0)
wrong = broken_distances(small, 0)
print("درست :", [right[n] for n in range(8)])
print("معیوب:", [wrong[n] for n in range(8)])
print("هر دو همهٔ هشت گره را دیده‌اند؟", len(right) == len(wrong) == 8)
```

```text
درست : [0, 1, 3, 2, 3, 3, 2, 1]
معیوب: [0, 1, 6, 5, 4, 3, 2, 1]
هر دو همهٔ هشت گره را دیده‌اند؟ True
```

<div dir="rtl">

> ⚠️ **مواظب باش:** گرهٔ `2` فاصلهٔ واقعی‌اش `3` است و نسخهٔ معیوب می‌گوید `6`. **هیچ خطایی، هیچ هشداری، همهٔ هشت گره دیده‌شده، و یک `dict` کاملاً معقول به‌عنوان خروجی.** تنها چیزی که این را می‌گیرد، مقایسه با یک جوابِ مستقلاً درست است.

با `pop` دیگر صف نیست؛ `stack` است. **یعنی این تابع در واقع `DFS` است که خودش را «فاصله» صدا می‌زند** — و همان درسِ ترمِ ۲ فصلِ ۷ است، این بار با پیامدِ خیلی بدتر: آن‌جا `pop(0)` فقط کند بود، این‌جا `pop` **غلط** است.

## ۵. و اگر مجموعهٔ دیده‌شده‌ها را برداریم؟

در درخت هیچ گره‌ای دو پدر نداشت، پس هیچ‌وقت به جای تکراری نمی‌رسیدی. **در گراف، حلقه هست.**

</div>

```python
def dfs_no_seen(graph, node):
    """همان DFSِ بازگشتی، بدونِ مجموعهٔ دیده‌شده‌ها."""
    count = 1
    for nbr in graph[node]:
        count += dfs_no_seen(graph, nbr)
    return count


try:
    print(dfs_no_seen(small, 0))
except RecursionError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
RecursionError: maximum recursion depth exceeded
```

<div dir="rtl">

**گرهٔ `0` همسایهٔ `1` است و `1` همسایهٔ `0`** — همین دو خط برای یک رفت‌وبرگشتِ بی‌پایان کافی است. `seen` تنها چیزی است که جلوی این را می‌گیرد، و **در نسخهٔ حلقه‌ای هم به همان اندازه لازم است**؛ آن‌جا فقط به‌جای `RecursionError`، `queue` بی‌نهایت بزرگ می‌شود و نشستت بی‌صدا می‌میرد. **پس نسخه‌ای که `recursion` دارد این‌جا مهربان‌تر است: لااقل داد می‌زند.**

## ۶. `O(V+E)`، با شمارنده

هر دو پیمایش هر گره را یک بار از ظرف بیرون می‌آورند و هر یال را دو بار نگاه می‌کنند — یک بار از هر سرش. **پس کارِ کل باید دقیقاً `V + 2E` باشد.** این یک ادعاست؛ می‌سنجیمش.

</div>

```python
def sweep(graph):
    """از هر گرهِ دیده‌نشده یک BFS: (تعدادِ مؤلفه‌ها، کارِ شمرده‌شده)"""
    seen = set()
    components = 0
    work = 0
    for start in sorted(graph):
        if start in seen:
            continue
        components += 1
        seen.add(start)
        waiting = deque([start])
        while waiting:
            node = waiting.popleft()
            work += 1                       # یک گره از صف بیرون آمد
            for nbr in graph[node]:
                work += 1                   # یک یال نگاه شد
                if nbr not in seen:
                    seen.add(nbr)
                    waiting.append(nbr)
    return components, work


def make_graph(node_count, edge_count, seed=SEED):
    rng = random.Random(seed)
    edges = set()
    while len(edges) < edge_count:
        a = rng.randrange(node_count)
        b = rng.randrange(node_count)
        if a != b:
            edges.add((min(a, b), max(a, b)))
    graph = {node: [] for node in range(node_count)}
    for a, b in sorted(edges):
        graph[a].append(b)
        graph[b].append(a)
    for node in graph:
        graph[node].sort()
    return graph


check = make_graph(1_000, 3_000)
parts, work = sweep(check)
print("V =", len(check), "· E = 3,000 · مؤلفه‌ها:", parts, "· کارِ شمرده‌شده:", work)
print("برابرِ V + 2E است؟", work == len(check) + 2 * 3_000)
```

```text
V = 1000 · E = 3,000 · مؤلفه‌ها: 5 · کارِ شمرده‌شده: 7000
برابرِ V + 2E است؟ True
```

<div dir="rtl">

**`True`، و نه «تقریباً».** این یکی از معدود جاهای این دوره است که یک ادعای هزینه را می‌شود **دقیقاً** تأیید کرد، نه با ستونِ نسبت.

و یک نکتهٔ جانبیِ مهم هم در همین خروجی هست: **این گراف پنج مؤلفه دارد.** یعنی یک `BFS` از یک گرهِ دلخواه، همهٔ گراف را نمی‌بیند. `sweep` برای همین از **هر** گرهِ دیده‌نشده یک پیمایشِ تازه شروع می‌کند — و همان حلقهٔ بیرونی، شمارشِ مؤلفه‌ها را هم رایگان به تو می‌دهد.

> 🤔 **اول حدس بزن:** دو جدول می‌آید. در اولی `V` دو برابر می‌شود و `E` هم پابه‌پایش؛ در دومی `V` ثابت است و فقط `E` دو برابر می‌شود. **برای هر کدام ستونِ نسبت را حدس بزن** و بنویس.

</div>

```python
V_LADDER = [1_000, 2_000, 4_000, 8_000]
print("— V دو برابر می‌شود، E = 3V")
table([(v, sweep(make_graph(v, 3 * v))[1]) for v in V_LADDER], "کار", ",d")
print("\n— V = 4,000 ثابت، E دو برابر می‌شود")
print(f"{'E':>10}{'کار':>18}{'نسبت به سطر قبل':>20}")
previous = None
for e in (4_000, 8_000, 16_000, 32_000):
    w = sweep(make_graph(4_000, e))[1]
    ratio = "—" if not previous else f"{w / previous:.2f}"
    print(f"{e:>10,}{w:>18,}{ratio:>20}")
    previous = w
```

```text
— V دو برابر می‌شود، E = 3V
         n               کار     نسبت به سطر قبل
     1,000             7,000                   —
     2,000            14,000                2.00
     4,000            28,000                2.00
     8,000            56,000                2.00

— V = 4,000 ثابت، E دو برابر می‌شود
         E               کار     نسبت به سطر قبل
     4,000            12,000                   —
     8,000            20,000                1.67
    16,000            36,000                1.80
    32,000            68,000                1.89
```

<div dir="rtl">

**دو جدول لازم بود، و همین دلیلِ نوشتنِ `O(V+E)` به‌جای `O(V)` یا `O(E)` است.**

جدولِ اول `2.00` می‌دهد: وقتی هر دو با هم دو برابر شوند، کار هم دو برابر می‌شود. **این جدول به‌تنهایی نمی‌گوید کدام‌یک از `V` و `E` مسئولِ رشد است**، چون هر دو هم‌زمان عوض شده‌اند.

جدولِ دوم آن را باز می‌کند: با ثابت ماندنِ `V`، نسبت‌ها `1.67`، `1.80` و `1.89` می‌شوند — کمتر از `2` ولی رو به `2`. **دلیلش دقیقاً همان `V` ثابت است که در فرمول مانده:** در سطرِ اول `4,000` واحد از `12,000` مالِ گره‌هاست، یعنی یک‌سومِ کل؛ در سطرِ آخر همان `4,000` از `68,000` است، کمتر از یک‌پانزدهم. **هرچه یال‌ها بیشتر شوند، سهمِ `V` کمتر و نسبت به `2` نزدیک‌تر می‌شود.**

**و همین‌جا یک قاعدهٔ عملی درمی‌آید: پیمایشِ گراف تقریباً همیشه ارزان است.** گرانیِ کارهای گراف از پیمایش نمی‌آید؛ از کاری می‌آید که **چند بار** پیمایش می‌کند، یا بدتر، از کاری که می‌خواهد همهٔ مسیرها را ببیند. **فصلِ بعد دقیقاً دربارهٔ همان است.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک پیمایشِ کامل با شمارندهٔ دستی، در برابرِ فرمولِ `V + 2E`، روی گراف‌های تصادفیِ ساخته‌شده با `SEED` ثابت. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ گره با `E = 3V`، و `V = 4,000` ثابت با ۴٬۰۰۰ تا ۳۲٬۰۰۰ یال. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ شمارش قطعی است. **هیچ عددِ ثانیه‌ای در این فصل نیست.**

> ✅ **چک کن:** در `sweep` خطِ `work += 1` داخلِ حلقهٔ همسایه‌ها را بردار و جدولِ اول را دوباره بگیر. **کارِ شمرده‌شده باید دقیقاً `V` شود — `1,000`، `2,000`، `4,000`، `8,000` — و ستونِ نسبت هنوز `2.00` بماند.** یعنی ستونِ نسبت به تو نمی‌گوید کدام بخشِ کار را شمرده‌ای؛ **این را فقط از خودِ کد می‌شود فهمید.**

> 🔧 **اگر کار نکرد:** پرتکرارترین اشتباه در نوشتنِ `BFS` این است که یادت برود ظرف باید `deque` باشد و با یک `list` معمولی شروع کنی:

</div>

```python
try:
    waiting = [0]
    waiting.popleft()
except AttributeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
AttributeError: 'list' object has no attribute 'popleft'
```

<div dir="rtl">

**این خطا دوست‌داشتنی است، چون فوری بلند می‌شود.** خطرناکش وقتی است که به‌جای اضافه کردنِ `deque`، `popleft` را به `pop` تبدیل کنی تا خطا برود — **و آن‌وقت دقیقاً به تلهٔ بخشِ ۴ افتاده‌ای: کدی که اجرا می‌شود و جوابِ غلط می‌دهد.**

> 🤖 **از دستیارت بپرس:** **خروجیِ بخشِ ۴ را جلویش بگذار و بپرس:** «هر دو تابع همهٔ هشت گره را دیده‌اند؛ کدام‌شان فاصلهٔ درست می‌دهد و چرا؟» — جوابِ درست باید بگوید فاصله فقط وقتی درست است که گره‌ها به‌ترتیبِ فاصله باز شوند. بعد این را هم بپرس: **«اگر یال‌ها وزن داشته باشند، `BFS` باز هم کوتاه‌ترین مسیر را می‌دهد؟»**

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `BFS` | بی‌اف‌اس | پیمایشِ سطح‌به‌سطح با `queue` |
| `DFS` | دی‌اف‌اس | پیمایشِ عمقی با `stack` |
| visited set | ویزیتد ست | مجموعهٔ دیده‌شده‌ها: چیزی که جلوی برگشتن به گرهِ تکراری را می‌گیرد |
| shortest path | شورتست پث | کوتاه‌ترین مسیر: کم‌یال‌ترین راه بینِ دو گره |
| connected component | کانکتد کامپوننت | مؤلفه: تکه‌ای از گراف که از بیرونش هیچ راهی به آن نیست |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا `BFS` کوتاه‌ترین مسیر می‌دهد ولی `DFS` نه؟

**تمرینِ اجباری:** تابعی بنویس که اندازهٔ بزرگ‌ترین مؤلفهٔ یک گراف را برگرداند. **حالا جدولِ چهار اندازه‌ای‌اش را برای `E = V`، `E = 2V` و `E = 3V` بگیر.** سؤالِ اصلی: **از کدام نسبتِ `E` به `V` به بعد تقریباً همهٔ گراف یک مؤلفه می‌شود؟** جوابت باید یک عدد باشد و یک جدول پشتش.

**تمرینِ ستاره‌دار ⭐:** `dfs_path` را طوری تغییر بده که به‌جای اولین مسیر، **کوتاه‌ترین** مسیر را برگرداند (همهٔ مسیرها را ببیند و بهترین را نگه دارد). **قبل از اجرا پیش‌بینی کن** جوابش با `bfs_path` یکی می‌شود یا نه، و **هزینه‌اش چند برابرِ `BFS` می‌شود**. حالا هر دو را روی همان گرافِ هشت‌گره‌ای با شمارنده اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و سؤالِ آخر: روی یک گرافِ ۱٬۰۰۰ گره‌ای هم می‌شود این کار را کرد؟**

## در فصل بعد

آخرین تمرین یک درِ خطرناک را باز کرد: «همهٔ مسیرها را ببین». **فصلِ بعد آن در را کاملاً باز می‌کند و می‌بینی پشتش چیست.**

روی گرافِ کاملِ یازده‌گره‌ای، تعدادِ مسیرهای ساده از یک گره به گرهِ دیگر `986,410` است و ستونِ نسبتش `7.00`، `8.00`، `9.00` — **نسبتی که خودش با `n` بزرگ می‌شود.** آن‌جا هم می‌بینی که با یک ماشینِ هزار برابر سریع‌تر، بزرگ‌ترین `n`ی که برای یک کارِ `O(n!)` می‌شود حل کرد، از `12` به `14` می‌رود.

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t5/s06-bfs-dfs (یادستان, Yaadestan)
