Published by Dimitris Kougioumtzis · Updated
Treat edges as undirected. Grow a tree from its lightest connecting edge; restart for disconnected components.
Choose the lightest edge leaving the reached set, restarting at another component when needed.
When to use Prim minimum spanning forest
Minimum-cost undirected connectivity.
Choosing an alternative
Kruskal globally orders edges instead of growing one frontier.
Worked example: input and state changes
Example input
0,1,4; 0,2,2; 2,1,1; 1,3,5; 2,3,8; 3,4,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial undirected graph.
State at this checkpoint
{ "values": [ "∞", "∞", "∞", "∞", "∞" ], "active": [], "kind": "graph", "visited": [], "chosen": [] }Step 3: Improve connecting edge to node 2, weight 2.
State at this checkpoint
{ "values": [ 0, 4, 2, "∞", "∞" ], "active": [ 0, 2 ], "kind": "graph", "visited": [ 0 ], "chosen": [] }Step 6: Improve connecting edge to node 3, weight 8.
State at this checkpoint
{ "values": [ 0, 1, 2, 8, "∞" ], "active": [ 2, 3 ], "kind": "graph", "visited": [ 0, 2 ], "chosen": [ 1 ] }Step 9: Include node 3; total weight 8.
State at this checkpoint
{ "values": [ 0, 1, 2, 5, "∞" ], "active": [ 3 ], "kind": "graph", "visited": [ 0, 2, 1, 3 ], "chosen": [ 1, 2, 3 ] }Step 12: Minimum spanning tree weight: 10.
State at this checkpoint
{ "values": [ 0, 1, 2, 5, 2 ], "active": [], "kind": "graph", "visited": [ 0, 2, 1, 3, 4 ], "chosen": [ 1, 2, 3, 5 ] }
Expected final state
Minimum spanning tree weight: 10.
Complexity and input bounds
Family: Graphs. Time complexity: O(V² + VE).
Space complexity: O(V) keys, parents, and visited state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Directed edges as source,target,weight; separated by semicolons. Nodes 0–7, positive weights 1–99. Start node is 0.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
A Prim key is a connection edge cost, not a source-to-node shortest distance.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | // Directed edge arrays from, to, weight; nodes 0..vertices-1; source 0. Up to 8 vertices, 16 edges. Allocate output with at least 256 integers. Treats edges as undirected. Writes selected edge indices; returns minimum spanning forest weight. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(from, to, weight, edges, vertices, output) { let key = Array(256).fill(0); let parent = Array(256).fill(0); let seen = Array(256).fill(0); for (let v = 0; v < vertices; v++) { key[v] = 1000000; parent[v] = -1; } let count = 0; let total = 0; for (let step = 0; step < vertices; step++) { let u = -1; for (let v = 0; v < vertices; v++) { if (seen[v] == 0 && (u < 0 || key[v] < key[u])) { u = v; } } if (key[u] == 1000000) { key[u] = 0; } seen[u] = 1; if (parent[u] >= 0) { output[count++] = parent[u]; total += key[u]; } for (let i = 0; i < edges; i++) { let v = -1; if (from[i] == u) { v = to[i]; } else if (to[i] == u) { v = from[i]; } if (v >= 0 && seen[v] == 0 && weight[i] < key[v]) { key[v] = weight[i]; parent[v] = i; } } } return total; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- Shortest Connection Networks And Some Generalizations
R. C. Prim (1957). Research paper.