This guide explains Prim's Algorithm from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Prim's Algorithm belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
از یک رأس شروع میکنیم و هر بار کمهزینهترین یال به یک رأس جدید را انتخاب میکنیم.
Step-by-step process
- یک رأس وارد MST میشود.
- یالهای کاندید در Min-Heap قرار میگیرند.
- کموزنترین یال به رأس جدید انتخاب میشود.
- تا پوشش همه رأسها ادامه میدهیم.
JavaScript example
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;
}Real-world and workplace examples
- کابلکشی کمهزینه
- اتصال دیتاسنترها
- شبکه برق و فیبر
- Backbone Network
Time and space complexity
با Heap about O(E log V)
When should you use it?
Use it when the problem matches this condition: ساخت Minimum Spanning Tree.
When is it not a good fit?
It is usually not the best choice when: برای shortest path مناسب نیست..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.