درخت پوشای کمینه: مقایسه الگوریتم‌های کروسکال و پریم

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

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

مثال گراف با یال‌های وزن‌دار:
A-B: 4    A-C: 8
B-C: 8    B-D: 11
C-D: 7    C-E: 2
D-E: 6    D-F: 4
E-F: 14

درخت پوشای کمینه همه رأس‌ها را متصل می‌کند
با استفاده از کوچک‌ترین وزن کل یال ممکن،
و دقیقاً (V-1) یال بدون چرخه انتخاب می‌کند

الگوریتم عمومی MST و ویژگی برش

هر دو الگوریتمی که در این مقاله پوشش داده می‌شوند نمونه‌های خاصی از یک قضیه عمومی‌تر هستند که یک رویکرد حریصانه به این مسئله را توجیه می‌کند. یک Cut (برش) یک گراف را به‌عنوان یک افراز رأس‌هایش به دو مجموعه مجزا تعریف کن، و یک یال Crosses (عبور می‌کند) از برش اگر یک رأس در یک مجموعه را به یک رأس در دیگری متصل کند.

ویژگی برش (بیان غیررسمی):
برای هر برش از گراف، اگر یک یال عبورکننده از برش
وزن دقیقاً کوچک‌تری از هر یال دیگر عبورکننده
از همان برش داشته باشد، آن یال باید در
هر درخت پوشای کمینه گنجانده شود

این قضیه، قابل‌اثبات با استفاده از یک استدلال تبادلی مشابه از نظر سبک با آن‌هایی که برای الگوریتم‌های حریصانه که پیش‌تر در این مجموعه بحث شد استفاده شدند، پایه‌ای است که هم الگوریتم کروسکال و هم پریم روی آن ساخته می‌شوند: هر دو الگوریتم به‌طور مکرر یک "یال ایمن" — یکی که توسط ویژگی برش تضمین می‌شود به برخی درخت پوشای کمینه تعلق دارد — شناسایی می‌کنند و آن را به راه‌حل در حال رشد اضافه می‌کنند.

الگوریتم کروسکال: مرتب‌سازی سراسری یال‌ها

Kruskal's Algorithm (الگوریتم کروسکال) همه یال‌ها را به ترتیب افزایشی وزن در نظر می‌گیرد، و هر یال را به جنگل در حال رشد اضافه می‌کند مگر اینکه این کار یک چرخه ایجاد کند.

MST-KRUSKAL(G, w):
  A = مجموعه خالی
  برای هر رأس v در G.V:
      MAKE-SET(v)
  یال‌های G.E را بر اساس وزن، به ترتیب غیرکاهشی مرتب کن
  برای هر یال (u, v)، به ترتیب مرتب‌شده:
      اگر FIND-SET(u) ≠ FIND-SET(v):
          A = A ∪ {(u, v)}
          UNION(u, v)
  A را برگردان

این الگوریتم مستقیماً به ساختار جنگل مجموعه‌مجزا که پیش‌تر در این مجموعه بحث شد متکی است تا به‌طور کارآمد بررسی کند آیا افزودن یک یال یک چرخه ایجاد می‌کند: دو رأس از قبل متصل‌اند اگر و فقط اگر به همان مجموعه‌مجزا تعلق داشته باشند، به این معنا که افزودن یک یال بین آن‌ها یک چرخه را می‌بندد نه اینکه درخت را گسترش دهد.

ردیابی الگوریتم کروسکال

یال‌های مرتب‌شده: C-E(2), A-B(4), D-F(4), D-E(6), C-D(7),
              A-C(8), B-C(8), B-D(11), E-F(14)

پردازش C-E(2): مجموعه‌های متفاوت → اضافه کن. MST: {C-E}
پردازش A-B(4): مجموعه‌های متفاوت → اضافه کن. MST: {C-E, A-B}
پردازش D-F(4): مجموعه‌های متفاوت → اضافه کن. MST: {C-E, A-B, D-F}
پردازش D-E(6): مجموعه‌های متفاوت → اضافه کن. MST: {C-E, A-B, D-F, D-E}
پردازش C-D(7): همان مجموعه (C-E-D-F متصل) → رد کن، چرخه ایجاد می‌کرد
پردازش A-C(8): مجموعه‌های متفاوت → اضافه کن. MST: {C-E, A-B, D-F, D-E, A-C}
(5 یال اکنون همه 6 رأس را متصل می‌کنند — MST کامل)

از آنجا که مرتب‌سازی یال‌ها زمان O(E log E) می‌گیرد، و پردازش هر یال با عملیات‌های مجموعه‌مجزای تقریباً-زمان-ثابتی که پیش‌تر در این مجموعه بحث شد زمان کل O(E α(V)) می‌گیرد، زمان اجرای کلی توسط مرتب‌سازی غالب است: O(E log E)، که معادل O(E log V) است چون E حداکثر V² است.

الگوریتم پریم: رشد یک درخت واحد

Prim's Algorithm (الگوریتم پریم) رویکرد متفاوتی اتخاذ می‌کند: به‌جای در نظر گرفتن سراسری یال‌ها، یک درخت واحد را از یک رأس دلخواه شروع کرده و رشد می‌دهد، و همیشه ارزان‌ترین یالی که درخت فعلی را به یک رأس جدید هنوز شامل‌نشده متصل می‌کند اضافه می‌کند.

MST-PRIM(G, w, r):
  برای هر رأس u در G.V:
      u.key = infinity
      u.p = NIL
  r.key = 0
  Q = صف اولویت حاوی همه رأس‌های G.V، کلیددهی‌شده با .key
  تا زمانی که Q خالی نباشد:
      u = EXTRACT-MIN(Q)
      برای هر v در Adj[u]:
          اگر v در Q باشد و w(u, v) < v.key:
              v.p = u
              v.key = w(u, v)      // عملیات DECREASE-KEY
  // یال‌های (v, v.p) برای همه v ≠ r، MST را تشکیل می‌دهند

این الگوریتم مستقیماً به ساختار صف اولویت که پیش‌تر در این مجموعه درباره هیپ‌ها بحث شد متکی است: در هر گام، رأس نزدیک‌ترین به درخت در حال رشد را به‌طور کارآمد استخراج می‌کند، و کلیدهای رأس‌های همسایه را وقتی یال‌های اتصال جدید و ارزان‌تر کشف می‌شوند به‌روزرسانی می‌کند.

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

شروع از رأس A:
استخراج A (کلید 0). به‌روزرسانی: B.key=4, C.key=8
استخراج B (کلید 4). به‌روزرسانی: (بدون بهبود، C.key در 8 می‌ماند)
استخراج C (کلید 8، از طریق A). به‌روزرسانی: D.key=7, E.key=2
استخراج E (کلید 2، از طریق C). به‌روزرسانی: D.key=6 (بهبودیافته)، F.key=14
استخراج D (کلید 6، از طریق E). به‌روزرسانی: F.key=4 (بهبودیافته، از طریق D)
استخراج F (کلید 4، از طریق D)

یال‌های MST حاصل: A-B, A-C, C-E, D-E, D-F

با استفاده از یک هیپ دودویی برای صف اولویت، هرکدام از V فراخوانی EXTRACT-MIN هزینه O(log V) دارد، و در سراسر همه تکرارها، حداکثر E عملیات DECREASE-KEY رخ می‌دهد، هرکدام نیز هزینه O(log V)، که زمان اجرای کل O(E log V) می‌دهد — که با پیچیدگی مجانبی الگوریتم کروسکال مطابقت دارد، هرچند دو الگوریتم از طریق مکانیزم‌های بسیار متفاوتی به آنجا