بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۶ از ۸

پیشرفت ترم
۰٪

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

دو پیمایشِ فصلِ ۲ را روی گراف می‌بریم. کد تقریباً همان است — یکی 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 درمی‌آید.

دو موجِ متفاوت که از یک گرهِ واحد در یک شبکه پخش می‌شوند: یکی حلقه‌های هم‌مرکز و دیگری یک رشتهٔ باریکِ عمیق

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

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

قبل از شروع#

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

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

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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]}")
گرهٔ 0: [1, 7]
گرهٔ 1: [0, 3]
گرهٔ 2: [3]
گرهٔ 3: [1, 2, 4]
گرهٔ 4: [3, 5]
گرهٔ 5: [4, 6]
گرهٔ 6: [5, 7]
گرهٔ 7: [0, 6]

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

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

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)))
BFS از گرهٔ ۰: [0, 1, 7, 3, 6, 2, 4, 5]
DFS از گرهٔ ۰: [0, 1, 3, 2, 4, 5, 6, 7]
هر دو همان گره‌ها را دیده‌اند؟ True

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

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

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

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

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:])))
مسیرِ BFS: [0, 7] · طول: 1 یال
مسیرِ DFS: [0, 1, 3, 4, 5, 6, 7] · طول: 6 یال
هر دو مسیرِ معتبرند؟ True

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

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

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

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

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

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])
فاصله‌های BFS        : [0, 1, 3, 2, 3, 3, 2, 1]
کمینه روی همهٔ مسیرها: [0, 1, 3, 2, 3, 3, 2, 1]
هر هشت گره یکی درآمدند؟ True
و مسیرِ DFS تا گرهٔ ۷: 6 یال — برابرِ کوتاه‌ترین؟ False

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

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

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

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

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)
درست : [0, 1, 3, 2, 3, 3, 2, 1]
معیوب: [0, 1, 6, 5, 4, 3, 2, 1]
هر دو همهٔ هشت گره را دیده‌اند؟ True

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

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

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

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

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}")
RecursionError: maximum recursion depth exceeded

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

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

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

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)
V = 1000 · E = 3,000 · مؤلفه‌ها: 5 · کارِ شمرده‌شده: 7000
برابرِ V + 2E است؟ True

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

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

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

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
— 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

دو جدول لازم بود، و همین دلیلِ نوشتنِ 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 معمولی شروع کنی:

try:
    waiting = [0]
    waiting.popleft()
except AttributeError as err:
    print(f"{type(err).__name__}: {err}")
AttributeError: 'list' object has no attribute 'popleft'

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

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

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

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

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

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

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

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.