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