الگوریتم پریم

حریصانه

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

پریم هم درخت پوشای کمینه می‌سازد، ولی برخلاف کروسکال آن را از یک گره رشد می‌دهد. در هر لحظه یک درخت داریم (in_tree). از بین همه‌ی یال‌هایی که گره‌ای از درخت را به گره‌ای بیرون از آن وصل می‌کنند، سبک‌ترین را برمی‌داریم و گره‌ی تازه را به درخت اضافه می‌کنیم.

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

زمان: O((V + E) log V)
حافظه: O(V + E)
CLRS، بخش ۲۱.۲
هوروویتز–ساهنی، فصل ۶
گریمالدی، فصل ۱۳

ورودی:

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

همان گراف نه‌گره‌ای مثال کروسکال، این بار با رشد از A؛ وزن درخت باز هم ۳۷ است.

from heapq import heappop, heappush
INF = float("inf")
def prim(graph, src):
key = {v: INF for v in graph}
parent = {v: None for v in graph}
key[src] = 0
pq = [(0, src)]
in_tree = set()
while pq:
k, u = heappop(pq)
if u in in_tree:
continue
in_tree.add(u)
for v, w in graph[u]:
if v not in in_tree:
if w < key[v]:
key[v] = w
parent[v] = u
heappush(pq, (w, v))
return parent, key

ناوردا: یال‌های parent بین گره‌های in_tree همیشه بخشی از یک درخت پوشای کمینه‌اند.

شروع اجرا

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

صف اولویت `pq`

خالی

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

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

prim()خط 6

گام ۱ از ۱۷۵

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

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

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

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

n	comparisons	update
4	5.2	4.4
8	13.8	11
12	20.8	16
16	28	22.8
20	35.4	28.4
24	37.2	32.4
28	47.2	40

توضیح

ایده

key و صف اولویت

برای هر گره‌ی بیرون از درخت، key[v] وزن سبک‌ترین یالی است که تا الان می‌شناسیم و v را به درخت وصل می‌کند. پیدا کردن گره با کمترین key با صف اولویت انجام می‌شود، دقیقاً مثل Dijkstra:

گره با کمترین key از صف بیرون می‌آید. اگر قبلاً در درخت بوده، رد می‌شود.
به درخت اضافه می‌شود.
برای هر همسایه‌ی v بیرون از درخت: اگر یال u — v از key[v] سبک‌تر است، key[v] و parent[v] به‌روز می‌شوند و v با کلید تازه وارد صف می‌شود.

فرق با Dijkstra

ساختار دو الگوریتم یکی است و فقط شرط فرق دارد: Dijkstra می‌پرسد dist[u] + w < dist[v] (طول کل مسیر از مبدأ)، ولی پریم فقط w < key[v] (وزن همان یک یال). برای همین درخت Dijkstra کوتاه‌ترین مسیرها را می‌دهد و درخت پریم کمترین وزن کل را.

هزینه

با صف اولویت دودویی O((V + E) log V).

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

عدد کنار هر گره key آن است؛ یال‌های آبی (از parent) درخت تا اینجا هستند.
در ورودی «گراف کامل» صف اولویت پر از عضوهای کهنه (خط‌خورده) می‌شود.
درخت نهایی را با نتیجه‌ی کروسکال روی همان گراف («مثال به سبک کتاب») مقایسه کن: وزن کل هر دو ۳۷ است.