درخت پوشای کمینه

درخت پوشای کمینه (MST): اتصال همه رأس‌ها با کمترین هزینه کل؛ الگوریتم‌های Prim و Kruskal

مسئله MST چیست؟

درخت پوشای کمینه (Minimum Spanning Tree): در گراف وزن‌دار همبند، درختی پیدا کن که همه رأس‌ها را با کمترین مجموع وزن یال‌ها به هم وصل کند.

مثال کلاسیک: شرکت مخابراتی می‌خواهد کابل به همه روستاها برساند؛ کابل‌ها گران‌اند — کدام یال‌ها را بگذارد که همه متصل شوند با کمترین هزینه؟

دو الگوریتم طمع‌کارانه معروف

۱. Prim — رشد از یک نقطه

مثل خزه‌ای که از یک رأس پخش می‌شود:

  1. از یک رأس دلخواه شروع
  2. از همه یال‌های بین «داخل درخت» و «بیرون»، سبک‌ترین را بردار
  3. رأس جدید به درخت اضافه شد — تکرار تا پوشش همه

پیاده‌سازی با هیپ: O(E log V) — شبیه دایکسترا!

۲. Kruskal — مرتب‌سازی یال‌ها

از سبک به سنگین، یال‌ها را یکی‌یکی:

  1. همه یال‌ها را بر اساس وزن مرتب کن
  2. سبک‌ترین یال را بردار؛ اگر دور نمی‌سازد، به درخت اضافه کن
  3. تکرار تا n−1 یال

تشخیص دور با ساختار Union-Find: O(E log E)

مثال کوچک — هر دو یک جواب

    1
A ----- B
|       |
4|       |2
|  3    |
C ----- D

Prim از A: A-B(1), B-D(2), A-C(4)  = 7
Kruskal:   A-B(1), B-D(2), A-C(4)  = 7 ✓

مقایسه Prim و Kruskal

ویژگیPrimKruskal
رویکردرشد از یک رأسمرتب‌سازی یال‌ها
پیچیدگیO(E log V)O(E log E)
مناسب برایگراف پر یال (Dense)گراف کم‌یال (Sparse)
ساختار کلیدیهیپUnion-Find
درخت در طول اجراهمیشه متصل ✓جنگل (تکه‌تکه)

کاربردهای واقعی

نکته: تفاوت با دایکسترا: MST مجموع وزن کل مسیر را کمینه می‌کند (نه مسیر تک‌به‌تک!). مسیر A تا B در MST ممکن است از کوتاه‌ترین مسیرشان طولانی‌تر باشد.

جمع‌بندی

این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.

ابزارهای مرتبط