Prim's Algorithm یکی از الگوریتم‌های کلاسیک برای ساخت Minimum Spanning Tree (MST) در یک گراف وزن‌دار و بدون‌جهت است.

هدف Prim این نیست که کوتاه‌ترین مسیر از یک مبدأ به بقیه‌ی رأس‌ها را پیدا کند؛ هدف این است که:

تمام Vertexهای Graph را با کمترین مجموع Weight ممکن، بدون ایجاد Cycle، به هم متصل کند.

این تفاوت بسیار مهم است.

مثلاً اگر بخواهیم چند ساختمان، دیتاسنتر، ایستگاه، شهر یا Node شبکه را با کمترین هزینه‌ی کلی به هم متصل کنیم، مسئله می‌تواند به MST تبدیل شود.

در این مقاله Prim را از پایه بررسی می‌کنیم؛ از تعریف Tree و Spanning Tree گرفته تا Cut Property، Min-Heap، تفاوت با Kruskal و Dijkstra، Graphهای Dense/Sparse، Edge Caseها و پیاده‌سازی JavaScript و TypeScript.

Minimum Spanning Tree چیست؟

ابتدا سه مفهوم را جدا کنیم:

Tree

Graph بدون Cycle که Connected است.

برای V رأس، Tree دقیقاً:

V - 1

Edge دارد.

Spanning Tree

Treeای است که تمام Vertexهای Graph اصلی را پوشش دهد.

Minimum Spanning Tree

از میان همه‌ی Spanning Treeها، درختی که مجموع Weightهای Edgeهایش کمترین مقدار را داشته باشد.

مثال ساده

Graph:

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

ما باید Edgeهایی را انتخاب کنیم که:

• همه‌ی Nodeها Connected شوند،
• Cycle ایجاد نشود،
• مجموع Weight حداقل باشد.

مثلاً یک MST ممکن است:

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

باشد.

هزینه:

1 + 2 + 3 = 6

Prim دقیقاً چه کاری می‌کند؟

ایده Prim:

1. از یک Vertex شروع کن.
2. مجموعه‌ای از Vertexهای داخل MST نگه دار.
3. تمام Edgeهایی را که از MST فعلی به Vertex خارج آن می‌روند بررسی کن.
4. کم‌وزن‌ترین Edge را انتخاب کن.
5. Vertex جدید را وارد MST کن.
6. تا پوشش همه‌ی Vertexها ادامه بده.

شهود Prim

فرض کنید در حال ساخت شبکه هستیم.

ابتدا فقط یک Site داریم.

بعد هر بار می‌پرسیم:

ارزان‌ترین Connection فعلی که شبکه‌ی ساخته‌شده را به یک Site جدید متصل می‌کند چیست؟

Prim دقیقاً همین تصمیم را تکرار می‌کند.

چرا انتخاب Greedy درست است؟

Prim یک الگوریتم Greedy است.

در هر مرحله بهترین Edge محلی را انتخاب می‌کند.

دلیل درست بودن آن به یک ویژگی مهم MST برمی‌گردد:

Cut Property

Cut چیست؟

Cut یعنی تقسیم Vertexها به دو مجموعه:

S
V - S

مثلاً:

داخل MST فعلی
خارج MST فعلی

Edgeای که بین این دو مجموعه باشد:

Crossing Edge

نامیده می‌شود.

Cut Property

قانون اصلی:

اگر یک Cut داشته باشیم، کم‌وزن‌ترین Edgeای که از آن Cut عبور می‌کند، در حداقل یک MST قرار دارد.

Prim دقیقاً از همین قانون استفاده می‌کند.

در هر مرحله:

S = visited vertices
V-S = unvisited vertices

و ارزان‌ترین Edge بین این دو را انتخاب می‌کند.

مراحل Prim

فرض کنید از A شروع می‌کنیم.

visited = {A}

Edgeهای Candidate:

A-B = 1
A-C = 4

کمترین:

A-B = 1

پس B اضافه می‌شود.

حالا Candidateها ممکن است:

A-C = 4
B-C = 2
B-D = 5

کمترین:

B-C = 2

پس C اضافه می‌شود.

بعد:

C-D = 3
B-D = 5

کمترین:

C-D = 3

پس D اضافه می‌شود.

MST کامل شد.

چرا Cycle ایجاد نمی‌شود؟

Prim فقط Edgeای را انتخاب می‌کند که:

یک Vertex داخل MST
→ یک Vertex خارج MST

را متصل کند.

پس Vertex جدیدی وارد Tree می‌شود و Cycle ایجاد نمی‌شود.

نسخه ساده JavaScript

نسخه‌ی آموزشی:

function primSimple(graph, start) {
  const visited = new Set([start]);
  const mst = [];
  const candidates = [];

  for (const [to, weight] of graph[start] ?? []) {
    candidates.push([weight, start, to]);
  }

  while (candidates.length > 0) {
    candidates.sort((a, b) => a[0] - b[0]);

    const [weight, from, to] =
      candidates.shift();

    if (visited.has(to)) {
      continue;
    }

    visited.add(to);
    mst.push([from, to, weight]);

    for (const [next, cost] of graph[to] ?? []) {
      if (!visited.has(next)) {
        candidates.push([
          cost,
          to,
          next
        ]);
      }
    }
  }

  return mst;
}

این نسخه برای آموزش خوب است، اما به دلیل:

sort()
shift()

در هر مرحله برای Graph بزرگ مناسب نیست.

چرا Min-Heap بهتر است؟

Prim همیشه باید:

کم‌وزن‌ترین Candidate Edge

را بردارد.

این دقیقاً کاری است که:

Min-Heap / Priority Queue

برای آن مناسب است.

Min-Heap ساده در JavaScript

class MinHeap {
  constructor() {
    this.data = [];
  }

  push(item) {
    this.data.push(item);

    let i = this.data.length - 1;

    while (i > 0) {
      const p = Math.floor(
        (i - 1) / 2
      );

      if (
        this.data[p][0] <=
        this.data[i][0]
      ) {
        break;
      }

      [
        this.data[p],
        this.data[i]
      ] = [
        this.data[i],
        this.data[p]
      ];

      i = p;
    }
  }

  pop() {
    if (this.data.length === 0) {
      return null;
    }

    const root = this.data[0];
    const last = this.data.pop();

    if (this.data.length > 0) {
      this.data[0] = last;

      let i = 0;

      while (true) {
        let smallest = i;
        const left = i * 2 + 1;
        const right = i * 2 + 2;

        if (
          left < this.data.length &&
          this.data[left][0] <
            this.data[smallest][0]
        ) {
          smallest = left;
        }

        if (
          right < this.data.length &&
          this.data[right][0] <
            this.data[smallest][0]
        ) {
          smallest = right;
        }

        if (smallest === i) {
          break;
        }

        [
          this.data[i],
          this.data[smallest]
        ] = [
          this.data[smallest],
          this.data[i]
        ];

        i = smallest;
      }
    }

    return root;
  }

  get size() {
    return this.data.length;
  }
}

Prim با Min-Heap

function prim(graph, start) {
  const visited = new Set();
  const mst = [];
  const heap = new MinHeap();

  heap.push([0, null, start]);

  let totalWeight = 0;

  while (heap.size > 0) {
    const item = heap.pop();

    if (!item) break;

    const [weight, from, node] = item;

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    if (from !== null) {
      mst.push([
        from,
        node,
        weight
      ]);

      totalWeight += weight;
    }

    for (
      const [next, cost]
      of graph[node] ?? []
    ) {
      if (!visited.has(next)) {
        heap.push([
          cost,
          node,
          next
        ]);
      }
    }
  }

  return {
    mst,
    totalWeight,
    visitedCount: visited.size
  };
}

بررسی Connected بودن Graph

MST فقط وقتی برای کل Graph وجود دارد که Graph Connected باشد.

اگر:

visited.size !== numberOfVertices

باشد، Graph disconnected است.

در این حالت:

Minimum Spanning Tree

برای کل Graph نداریم.

اما می‌توانیم:

Minimum Spanning Forest

بسازیم.

Minimum Spanning Forest چیست؟

اگر Graph چند Component داشته باشد، برای هر Component یک MST جدا می‌سازیم.

مجموع آن‌ها:

Minimum Spanning Forest

است.

Prim برای Graph disconnected

می‌توانیم روی هر Vertex unvisited یک Prim جدید شروع کنیم.

function minimumSpanningForest(graph) {
  const allVisited = new Set();
  const forest = [];

  for (const start of Object.keys(graph)) {
    if (allVisited.has(start)) {
      continue;
    }

    const heap = new MinHeap();
    const tree = [];
    let cost = 0;

    heap.push([0, null, start]);

    while (heap.size > 0) {
      const [weight, from, node] =
        heap.pop();

      if (allVisited.has(node)) {
        continue;
      }

      allVisited.add(node);

      if (from !== null) {
        tree.push([
          from,
          node,
          weight
        ]);

        cost += weight;
      }

      for (
        const [next, edgeWeight]
        of graph[node] ?? []
      ) {
        if (!allVisited.has(next)) {
          heap.push([
            edgeWeight,
            node,
            next
          ]);
        }
      }
    }

    forest.push({
      edges: tree,
      cost
    });
  }

  return forest;
}

Prim و Kruskal چه تفاوتی دارند؟

هر دو MST می‌سازند.

اما Style آن‌ها متفاوت است.

Prim

از یک Vertex شروع می‌کند و Tree را رشد می‌دهد.

grow one connected tree

Kruskal

تمام Edgeها را Global Sort می‌کند و Edgeها را یکی‌یکی انتخاب می‌کند اگر Cycle نسازند.

sort edges globally
+ Union-Find

مقایسه Prim و Kruskal

آیا Prim همیشه همان MST Kruskal را می‌دهد؟

اگر MST یکتا باشد:

Yes

هر دو همان Tree را می‌دهند.

اگر چند MST با Cost یکسان وجود داشته باشد، ممکن است Edgeهای متفاوت انتخاب کنند ولی:

total weight

یکسان باشد.

MST چه زمانی Unique است؟

اگر تمام Edge Weightها distinct باشند:

MST unique

است.

اما اگر Weightهای تکراری داشته باشیم، ممکن است چند MST مختلف با Cost یکسان وجود داشته باشد.

Prim با Equal Weights

در صورت Tie، انتخاب هر Candidate با همان Minimum Weight می‌تواند به یک MST معتبر منجر شود.

اگر خروجی deterministic می‌خواهیم، باید Tie-Breaker مشخص کنیم.

مثلاً:

weight
then source id
then destination id

Prim vs Dijkstra

این تفاوت یکی از رایج‌ترین سؤال‌هاست.

هر دو:

• Greedy هستند.
• Min-Heap استفاده می‌کنند.
• یک مجموعه visited/finalized دارند.

اما Objective متفاوت است.

Prim

می‌پرسد:

ارزان‌ترین Edge برای اتصال یک Vertex جدید چیست؟

Dijkstra

می‌پرسد:

کدام Vertex کمترین Distance از Source را دارد؟

مثال تفاوت Prim و Dijkstra

Prim ممکن است Edgeای با Weight کم را انتخاب کند حتی اگر Path از Source به آن Vertex مجموعاً زیاد باشد.

چون Prim به:

Total Tree Weight

اهمیت می‌دهد، نه Shortest Path from source.

MST ≠ Shortest Path Tree

این نکته بسیار مهم است.

MST

هدف:

minimize sum of selected edges

Shortest Path Tree

هدف:

for each v,
distance(source, v)
minimum

این دو هدف متفاوت‌اند.

آیا Weight منفی برای Prim مشکل است؟

خیر.

Prim می‌تواند با Negative Edge هم کار کند.

MST در Graph finite و Undirected همچنان تعریف دارد.

برخلاف Shortest Path، Cycle منفی مشکل -Infinity ایجاد نمی‌کند چون MST اصلاً Cycle انتخاب نمی‌کند.

مثال Negative Weight

A --(-5)-- B
B --2---- C
A --10--- C

Prim Edge:

A-B = -5

را با خیال راحت انتخاب می‌کند.

آیا Graph باید Undirected باشد؟

MST کلاسیک برای:

Weighted Undirected Graph

تعریف می‌شود.

برای Directed Graph مفهوم متفاوتی داریم:

Minimum Spanning Arborescence

که الگوریتم‌هایی مثل:

Chu-Liu / Edmonds

برای آن مطرح‌اند.

پس Prim را مستقیم روی Directed Graph به‌عنوان MST استفاده نکنید.

Representation مناسب

برای Prim معمولاً:

Adjacency List

مناسب است.

مثلاً:

const graph = {
  A: [
    ["B", 1],
    ["C", 4]
  ],
  B: [
    ["A", 1],
    ["C", 2]
  ]
};

چون باید Neighborهای Vertex جدید را سریع وارد Heap کنیم.

Graph بدون‌جهت را دوطرفه ثبت کنید

برای Edge:

A -- B weight 3

Adjacency List باید:

A: [["B", 3]]
B: [["A", 3]]

داشته باشد.

Complexity با Binary Heap

با adjacency list و Binary Min-Heap:

O(E log E)

برای نسخه‌ی Edge-based Heap معمول است.

از آنجا که:

E <= V²

معمولاً به صورت:

O(E log V)

هم بیان می‌شود.

Complexity نسخه Key-Based Prim

نسخه‌ی دیگری از Prim برای هر Vertex:

key[v]

نگه می‌دارد؛ یعنی کمترین هزینه‌ی فعلی برای وصل کردن آن Vertex به MST.

با Heap مناسب:

O(E log V)

است.

Prim با Adjacency Matrix

برای Graph Dense می‌توان بدون Heap و با Matrix اجرا کرد.

هر بار Vertex با کمترین key را در:

O(V)

پیدا می‌کنیم.

این کار V بار تکرار می‌شود.

پس:

O(V²)

است.

برای Dense Graph این روش می‌تواند مناسب باشد.

Key-Based Prim

function primMatrix(matrix) {
  const n = matrix.length;

  const inMST = Array(n).fill(false);
  const key = Array(n).fill(Infinity);
  const parent = Array(n).fill(-1);

  key[0] = 0;

  for (let count = 0; count < n; count++) {
    let u = -1;

    for (let v = 0; v < n; v++) {
      if (
        !inMST[v] &&
        (
          u === -1 ||
          key[v] < key[u]
        )
      ) {
        u = v;
      }
    }

    if (u === -1) {
      break;
    }

    inMST[u] = true;

    for (let v = 0; v < n; v++) {
      const w = matrix[u][v];

      if (
        w !== Infinity &&
        !inMST[v] &&
        w < key[v]
      ) {
        key[v] = w;
        parent[v] = u;
      }
    }
  }

  return {
    parent,
    key
  };
}

Edge-Based vs Vertex-Key Prim

دو Style رایج داریم:

Edge-based

Heap شامل:

[weight, from, to]

است.

ساده و مناسب آموزش.

Key-based

برای هر Vertex بهترین Edge ورودی فعلی را نگه می‌داریم.

Heap شامل:

[key, vertex]

است.

این Style از نظر تئوری بسیار رایج است.

Stale Entries در Heap

اگر Priority Queue قابلیت Decrease-Key نداشته باشد، ممکن است چند Entry برای یک Vertex داشته باشیم.

راه رایج:

• Entry جدید را Push کن.
• هنگام Pop اگر Node قبلاً visited بود Ignore کن.

این تکنیک در Dijkstra هم رایج است.

مثال دنیای واقعی: کابل‌کشی

فرض کنید چند Building داریم.

هر Edge نشان‌دهنده‌ی هزینه کابل‌کشی مستقیم بین دو Building است.

می‌خواهیم همه Buildingها Connected باشند اما مجموع کابل حداقل شود.

این دقیقاً MST است.

Data Center Interconnect

Nodeها:

Data Center / Rack / Zone

Edge Weight:

cost of link

Prim می‌تواند یک Backbone کم‌هزینه‌ی ساختاری پیشنهاد دهد.

اما در سیستم واقعی فقط Cost مهم نیست؛ معمولاً Redundancy هم لازم است.

یک MST هیچ Cycle ندارد و بنابراین ممکن است Single Point of Failure داشته باشد.

نکته مهم: MST و Reliability

MST کمترین Cost اتصال را می‌دهد، اما الزاماً Reliableترین Network نیست.

چون Tree:

V - 1 edges

دارد و هیچ مسیر جایگزینی ندارد.

پس قطع یک Bridge می‌تواند Network را Partition کند.

در Production ممکن است ابتدا MST برای baseline cost ساخته شود و سپس Redundant Links اضافه شوند.

شبکه برق

در مدل ساده:

Substation = Vertex
Connection cost = Edge weight

MST می‌تواند Cost اولیه اتصال را کمینه کند.

اما شبکه برق واقعی محدودیت‌های Flow، Capacity، Safety و Redundancy دارد.

Fiber Backbone

اگر Edge Weight برابر Cost حفاری یا Fiber باشد، MST می‌تواند شبکه‌ای با حداقل هزینه‌ی اتصال اولیه بسازد.

Road / Pipeline / Utility Network

MST برای طراحی اولیه‌ی:

• Road links
• Pipelines
• Water distribution
• Cable layout
• Sensor network

می‌تواند مدل پایه باشد.

البته Constraintهای واقعی باید جداگانه مدل شوند.

Clustering و MST

MST در بعضی روش‌های Clustering نیز استفاده می‌شود.

مثلاً:

1. MST بساز.
2. بزرگ‌ترین Edgeها را حذف کن.
3. Componentهای باقی‌مانده را Cluster در نظر بگیر.

این ایده به Single-Linkage Clustering نزدیک است.

Prim و Euclidean MST

اگر Vertexها Pointهای هندسی باشند و Weight برابر Euclidean Distance باشد، MST می‌تواند یک اتصال کم‌هزینه بین نقاط بسازد.

برای Datasetهای هندسی بزرگ الگوریتم‌های تخصصی‌تری هم وجود دارند.

MST و Cut Property

Cut Property فقط برای Prim نیست.

Kruskal هم عملاً از Propertyهای Cut/Cycle استفاده می‌کند.

این Property پایه‌ی اثبات درست بودن بسیاری از الگوریتم‌های MST است.

Cycle Property

یک Property مهم دیگر:

در یک Cycle، اگر Edgeای به‌طور یکتا سنگین‌ترین Edge باشد، آن Edge در هیچ MST قرار نمی‌گیرد.

این دیدگاه مکمل Cut Property است.

آیا Start Vertex مهم است؟

برای Cost نهایی MST:

اگر MST یکتا باشد، خیر.

اگر چند MST وجود داشته باشد، Start Vertex و Tie-Breaking ممکن است روی Edgeهای انتخابی اثر بگذارند.

اما Weight نهایی همچنان Minimum است.

Edge Case: یک Vertex

Graph:

A

MST:

[]

و Cost:

0

است.

Edge Case: Graph خالی

اگر Vertex نداریم، باید قرارداد API مشخص شود.

می‌توان:

MST = []
cost = 0

در نظر گرفت.

Edge Case: Disconnected Graph

MST برای کل Graph وجود ندارد.

یا باید Error بدهیم، یا Minimum Spanning Forest برگردانیم.

Edge Case: Duplicate Edge

اگر چند Edge بین دو Vertex باشد، مشکلی نیست.

Prim می‌تواند ارزان‌ترین Option را انتخاب کند.

Edge Case: Self-loop

Self-loop:

A -- A

هیچ Vertex جدیدی به Tree اضافه نمی‌کند.

پس باید Ignore شود.

Edge Case: Negative Edge

مجاز است.

Edge Case: Equal Weights

ممکن است چند MST وجود داشته باشد.

نسخه TypeScript

type NodeId = string;

type Neighbor = [
  node: NodeId,
  weight: number
];

type Graph =
  Record<NodeId, Neighbor[]>;

type MSTEdge = [
  from: NodeId,
  to: NodeId,
  weight: number
];

type PrimResult = {
  edges: MSTEdge[];
  totalWeight: number;
  connected: boolean;
};

function prim(
  graph: Graph,
  start: NodeId
): PrimResult {
  const nodes = new Set<NodeId>();

  for (
    const [u, neighbors]
    of Object.entries(graph)
  ) {
    nodes.add(u);

    for (const [v] of neighbors) {
      nodes.add(v);
    }
  }

  if (!nodes.has(start)) {
    return {
      edges: [],
      totalWeight: 0,
      connected: false
    };
  }

  const visited = new Set<NodeId>();

  const candidates:
    Array<[number, NodeId | null, NodeId]> = [
      [0, null, start]
    ];

  const edges: MSTEdge[] = [];
  let totalWeight = 0;

  while (candidates.length > 0) {
    candidates.sort(
      (a, b) => a[0] - b[0]
    );

    const [
      weight,
      from,
      node
    ] = candidates.shift()!;

    if (visited.has(node)) {
      continue;
    }

    visited.add(node);

    if (from !== null) {
      edges.push([
        from,
        node,
        weight
      ]);

      totalWeight += weight;
    }

    for (
      const [next, cost]
      of graph[node] ?? []
    ) {
      if (!visited.has(next)) {
        candidates.push([
          cost,
          node,
          next
        ]);
      }
    }
  }

  return {
    edges,
    totalWeight,
    connected:
      visited.size === nodes.size
  };
}

این نسخه برای خوانایی از sort استفاده می‌کند؛ در Production بهتر است Min-Heap واقعی استفاده شود.

چگونه نتیجه MST را Validate کنیم؟

برای Graph Connected با V Vertex:

MST باید:

V - 1

Edge داشته باشد.

همچنین:

• همه Vertexها پوشش داده شوند.
• Cycle نداشته باشد.
• مجموع Weight حداقل باشد.

برای Test می‌توان نتیجه Prim را با Kruskal مقایسه کرد.

خطاهای رایج

1. اشتباه گرفتن Prim با Dijkstra

Prim Shortest Path Tree نمی‌سازد.

2. استفاده روی Directed Graph

MST کلاسیک برای Undirected Graph است.

3. فراموش کردن Graph disconnected

ممکن است فقط MST یک Component ساخته شود.

4. استفاده از sort در هر Iteration

برای Graph بزرگ بهتر است Min-Heap واقعی داشته باشیم.

5. انتخاب Edge به Vertex visited

باعث Cycle یا پردازش اضافی می‌شود.

6. ثبت نکردن Edgeها دوطرفه

در Undirected Graph باید adjacency دوطرفه باشد.

7. فرض اینکه MST بیشترین Reliability را دارد

MST کمترین Cost را می‌دهد، نه بیشترین Redundancy.

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

وقتی:

• Weighted Undirected Graph داریم.
• می‌خواهیم همه Vertexها Connected شوند.
• کمترین مجموع Edge Weight مهم است.
• MST لازم داریم.
• Graph با Adjacency List یا Matrix داریم.
• طراحی Backbone کم‌هزینه مطرح است.

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

اگر Shortest Path از Source می‌خواهیم:

Dijkstra / Bellman-Ford / BFS

اگر Graph Directed است:

Directed MST / Arborescence

اگر Graph disconnected است و کل Graph مهم است:

Minimum Spanning Forest

اگر Redundancy و Fault Tolerance اولویت اصلی است، MST به تنهایی کافی نیست.

جدول تصمیم سریع

Complexity خلاصه

Prim با Matrix

O(V²)

Prim با Binary Heap + Adjacency List

O(E log V)

یا در Edge-based implementation:

O(E log E)

که از نظر مرتبه بسیار نزدیک‌اند.

Space

Adjacency List:

O(V + E)

و Heap/Visited نیز فضای اضافی نیاز دارند.

جمع‌بندی

Prim یک الگوریتم Greedy برای ساخت:

Minimum Spanning Tree

در Graph:

weighted
undirected
connected

است.

الگوی اصلی:

Start from one vertex
→ grow the tree
→ always choose the cheapest edge
   connecting visited to unvisited

پایه‌ی نظری آن:

Cut Property

است.

با Binary Heap و Adjacency List:

O(E log V)

و برای Dense Graph با Matrix:

O(V²)

قابل اجراست.

مهم‌ترین تفاوتی که باید همیشه به خاطر داشته باشید:

Prim
→ minimize total cost of connecting all vertices

Dijkstra
→ minimize distance from one source

و Pattern تشخیص مسئله:

آیا می‌خواهم همه Nodeها را وصل کنم؟
آیا مجموع هزینه‌ی Connectionها باید حداقل شود؟
آیا Cycle لازم نیست؟

→ Minimum Spanning Tree
→ Prim / Kruskal