Prim's Algorithm
Minimum Spanning Tree algorithm that grows MST from starting vertex. Uses priority queue for efficiency. Named after Robert Prim, it builds MST by starting from arbitrary vertex and repeatedly adding minimum weight edge that connects MST to a new vertex.
Visualization
Interactive visualization for Prim's Algorithm
Prim's MST Algorithm
• Time: O(E log V) with binary heap
• Greedy algorithm
• Grows MST from single vertex
Interactive visualization with step-by-step execution
Implementation
1function prim(graph: number[][][], start: number = 0): [number, number, number][] {
2 const n = graph.length;
3 const visited = new Array(n).fill(false);
4 const mst: [number, number, number][] = [];
5 const pq: [number, number, number][] = []; // [weight, from, to]
6
7 visited[start] = true;
8 for (const [v, weight] of graph[start]) {
9 pq.push([weight, start, v]);
10 }
11
12 pq.sort((a, b) => a[0] - b[0]);
13
14 while (pq.length > 0 && mst.length < n - 1) {
15 const [weight, u, v] = pq.shift()!;
16
17 if (visited[v]) continue;
18
19 visited[v] = true;
20 mst.push([u, v, weight]);
21
22 for (const [next, w] of graph[v]) {
23 if (!visited[next]) {
24 pq.push([w, v, next]);
25 pq.sort((a, b) => a[0] - b[0]);
26 }
27 }
28 }
29
30 return mst;
31}Deep Dive
Theoretical Foundation
Prim's algorithm builds MST by starting with arbitrary vertex and growing the tree one vertex at a time. Maintains a cut between vertices in MST and vertices not yet included. Always selects minimum weight edge crossing this cut. Uses priority queue to efficiently find minimum weight edge. Unlike Kruskal which considers all edges globally, Prim works locally from current MST. Time: O((V + E) log V) with binary heap, O(V²) with simple array, O(E + V log V) with Fibonacci heap.
Complexity
Time
O((V + E) log V)
O((V + E) log V)
O((V + E) log V)
Space
O(V)
Applications
Industry Use
Network design (telecommunications, computer networks)
Cable laying (minimize total cable length)
Circuit board design (minimize wire length)
Cluster analysis (minimum spanning tree clustering)
Approximation algorithms for TSP
Image segmentation and computer vision
Social network analysis
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.