الگوریتم کروسکال
یال‌ها را از سبک به سنگین مرور می‌کند و هر یالی را که دور نمی‌سازد به درخت پوشای کمینه اضافه می‌کند.
درخت پوشای کمینه (MST) زیرمجموعه‌ای از یال‌های یک گراف همبند و بی‌جهت است که همه‌ی گره‌ها را به هم وصل می‌کند، دور ندارد و جمع وزن‌هایش کمترین مقدار ممکن است.
ادامه‌ی توضیح ↓- زمان:
O(E log E) - حافظه:
O(V + E) - CLRS، بخش ۲۱.۲
- هوروویتز–ساهنی، فصل ۶
- گریمالدی، فصل ۱۳
گراف نه‌گره‌ای با ۱۴ یال؛ درخت پوشای کمینه ۸ یال و وزن کل ۳۷ دارد.
def kruskal(graph, src):# Kruskal does not need a start node; src is ignored.parent = {v: v for v in graph}edges = sorted((w, u, v) for u in graph for v, w in graph[u] if u < v)mst = []for w, u, v in edges:ru = find(parent, u)rv = find(parent, v)if ru == rv:continueparent[ru] = rvmst.append((u, v, w))return mstdef find(parent, x):while parent[x] != x:x = parent[x]return x
شروع اجرا
- گره‌ی جاری
- درخت پوشای کمینه تا اینجا
- یالِ در حال بررسی
متغیرهای محلی
نارنجی = در همین گام عوض شد
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
- kruskal()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- consider
- union
- ورودی فعلی (n=9)
نمایش به شکل جدول
| n | consider | union |
|---|---|---|
| 4 | 5.2 | 3 |
| 8 | 13.8 | 7 |
| 12 | 20.8 | 11 |
| 16 | 28 | 15 |
| 20 | 35.4 | 19 |
| 24 | 37.2 | 23 |
| 28 | 47.2 | 27 |
توضیح
ایده
درخت پوشای کمینه (MST) زیرمجموعه‌ای از یال‌های یک گراف همبند و بی‌جهت است که همه‌ی گره‌ها را به هم وصل می‌کند، دور ندارد و جمع وزن‌هایش کمترین مقدار ممکن است.
کروسکال یک الگوریتم حریصانه است: یال‌ها را از سبک به سنگین مرور می‌کند و هر یال را برمی‌دارد، مگر اینکه با یال‌های برداشته‌شده دور بسازد.
تشخیص دور با Union–Find
یال u — v وقتی دور می‌سازد که u و v از قبل به هم وصل باشند. برای فهمیدن این، هر گره در یک «مجموعه» است که با دیکشنری parent به شکل درخت نگه داشته می‌شود:
find(x)ازxآن‌قدر درparentبالا می‌رود تا به ریشه‌ی مجموعه برسد.- اگر ریشه‌ی
uوvیکی بود، یال رد می‌شود. وگرنهparent[ru] = rvدو مجموعه را یکی می‌کند و یال بهmstاضافه می‌شود.
هزینه
مرتب کردن یال‌ها O(E log E) است و بخش بیشتر زمان را می‌گیرد. این پیاده‌سازی ساده‌ی find در بدترین حالت می‌تواند کند شود؛ نسخه‌ی کتاب‌ها با «فشرده‌سازی مسیر» و «اتحاد بر اساس رتبه» آن را تقریباً O(1) می‌کند.
در trace به چه چیزی نگاه کنی
- یال‌های آبی درخت پوشای کمینه‌ی ساخته‌شده تا اینجا هستند و یال نارنجی همانی است که بررسی می‌شود.
- عدد کنار هر گره
parentآن است: با دنبال کردن این عددها به ریشه‌ی مجموعه می‌رسی. - در ورودی «گراف خودش درخت است» هیچ یالی رد نمی‌شود؛ در «ناهمبند» به‌جای یک درخت، دو درخت (جنگل) ساخته می‌شود.