الگوریتم Prim چیست؟ ساخت Minimum Spanning Tree از صفر تا صد

Prim تمام رأس‌ها را با کمترین هزینه کل و بدون چرخه در یک MST متصل می‌کند. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی می‌فهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیت‌های آن را بررسی می‌کنیم.

این الگوریتم چه مسئله‌ای را حل می‌کند؟

Prim's Algorithm زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطه‌ای را نشان می‌دهند و خروجی مورد انتظار دقیقاً چیست.

ایده اصلی به ساده‌ترین شکل

از یک رأس شروع می‌کنیم و هر بار کم‌هزینه‌ترین یال به یک رأس جدید را انتخاب می‌کنیم.

مراحل اجرا

1. یک رأس وارد MST می‌شود.
2. یال‌های کاندید در Min-Heap قرار می‌گیرند.
3. کم‌وزن‌ترین یال به رأس جدید انتخاب می‌شود.
4. تا پوشش همه رأس‌ها ادامه می‌دهیم.

نمونه کد JavaScript

function prim(graph, start) {
  const seen = new Set([start]), mst = [], edges = [];
  edges.push(...(graph[start] ?? []).map(([v,w]) => [w,start,v]));
  while (edges.length) {
    edges.sort((a,b)=>a[0]-b[0]);
    const [w,u,v] = edges.shift();
    if (seen.has(v)) continue;
    seen.add(v); mst.push([u,v,w]);
    for (const [to,cost] of graph[v] ?? [])
      if (!seen.has(to)) edges.push([cost,v,to]);
  }
  return mst;
}

مثال‌های واقعی و دنیای کار

• کابل‌کشی کم‌هزینه
• اتصال دیتاسنترها
• شبکه برق و فیبر
• Backbone Network

پیچیدگی زمانی و فضایی

با Heap حدود O(E log V)

چه زمانی استفاده کنیم؟

ساخت Minimum Spanning Tree

چه زمانی مناسب نیست؟

برای shortest path مناسب نیست.

جمع‌بندی

Prim's Algorithm را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگی‌های آن هم‌خوان باشد. مهم‌ترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.