الگوریتم بروفکا (سولین)

حریصانه

در هر دور، هر مؤلفه سبک‌ترین یالِ بیرون‌رونده‌اش را برمی‌دارد؛ تعداد مؤلفه‌ها هر دور دست‌کم نصف می‌شود.

قدیمی‌ترین الگوریتم درخت پوشای کمینه (۱۹۲۶). هر گره یک مؤلفه است. در هر دور:

ادامه‌ی توضیح ↓

زمان: O(E log V)
حافظه: O(V + E)
هوروویتز–ساهنی، فصل ۴
CLRS، فصل ۲۱

ورودی:

V=9 · E=14 · src=Aخروجی PDF

همان گراف نه‌گره‌ای کروسکال و پریم؛ درخت وزن کل ۳۷ دارد.

def boruvka(graph, src):
# Boruvka does not need a start node; src is ignored.
comp = {v: v for v in graph}
mst = []
rounds = 0
merged = True
while merged:
merged = False
rounds = rounds + 1
best = {}
for u in graph:
for v, w in graph[u]:
if comp[u] == comp[v]:
continue
c = comp[u]
edge = (w, min(u, v), max(u, v))
if c not in best or edge < best[c]:
best[c] = edge
for w, u, v in sorted(best.values()):
if comp[u] == comp[v]:
continue
mst.append((u, v, w))
old = comp[v]
for x in graph:
if comp[x] == old:
comp[x] = comp[u]
merged = True
return mst

ناوردا: سبک‌ترین یالی که از یک مؤلفه بیرون می‌رود همیشه در یک درخت پوشای کمینه هست، پس همه‌ی یال‌های mst امن‌اند.

شروع اجرا

گره‌ی جاری (u)
درخت پوشای کمینه تا اینجا
یالِ در حال بررسی

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict

'A': [('B', 4), ('H', 8)]
'B': [('A', 4), ('H', 11), ('C', 8)]
'C': [('B', 8), ('I', 2), ('F', 4), ('D', 7)]
'D': [('C', 7), ('F', 14), ('E', 9)]
'E': [('D', 9), ('F', 10)]
'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)]
'G': [('F', 2), ('I', 6), ('H', 1)]
'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)]
'I': [('C', 2), ('G', 6), ('H', 7)]

Call stack

boruvka()خط 1

گام ۱ از ۶۵۷

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

check
ورودی فعلی (n=9)

نمایش به شکل جدول

n	check
4	25.2
8	82.8
12	124.8
16	168
20	227.2
24	283.6
28	322

توضیح

ایده

قدیمی‌ترین الگوریتم درخت پوشای کمینه (۱۹۲۶). هر گره یک مؤلفه است. در هر دور:

هر مؤلفه سبک‌ترین یالی را که از آن بیرون می‌رود پیدا می‌کند.
همه‌ی این یال‌ها به درخت اضافه می‌شوند و مؤلفه‌هایشان یکی می‌شوند.

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

چرا سریع است؟

هر مؤلفه با دست‌کم یک مؤلفه‌ی دیگر یکی می‌شود، پس تعداد مؤلفه‌ها هر دور دست‌کم نصف می‌شود: حداکثر log V دور، هر دور O(E)، جمعاً O(E log V). چون کار هر مؤلفه مستقل است، این روش برای اجرای موازی هم مناسب است.

شکستن تساوی

اگر وزن‌ها برابر باشند، دو مؤلفه ممکن است یال‌های متفاوتی انتخاب کنند و دور بسازند. اینجا یال‌ها با (وزن، نام کوچک‌تر، نام بزرگ‌تر) مقایسه می‌شوند تا ترتیب همیشه یکتا باشد.

در trace به چه چیزی نگاه کنی

عدد کنار هر گره نام مؤلفه‌ی آن است؛ ببین بعد از هر دور چند مؤلفه می‌ماند.
دیکشنری best در پنل حافظه یال انتخابی هر مؤلفه است.