V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Prim's Minimum Spanning Tree

Grow one connected tree through the lightest crossing edge

Start small and keep the tree connected

Prim's algorithm starts from one vertex. At every step it considers edges with exactly one endpoint inside the current tree, chooses the lightest such edge, and brings the outside endpoint into the tree. After V - 1 choices, every vertex is connected.

Read the expanding cut

Green vertices and edges are already inside the tree. The amber edge is the lightest edge crossing from that set to an outside vertex. Advancing one step adds both the edge and the new vertex, so the selected structure remains connected at all times.

123456789ABCDEF

Start at A; the tree initially contains one vertex.

1function prim(edges: [number, number, number][], n: number, start: number): number {
2 const inTree = Array(n).fill(false);
3 inTree[start] = true;
4 let weight = 0, count = 1;
5 while (count < n) {
6 let best: [number, number, number] | null = null;
7 for (const [u, v, w] of edges) {
8 if (inTree[u] !== inTree[v] && (best === null || w < best[2])) best = [u, v, w];
9 }
10 if (best === null) break;
11 const nv = inTree[best[0]] ? best[1] : best[0];
12 inTree[nv] = true;
13 weight += best[2];
14 count++;
15 }
16 return weight;
17}
StartA
Tree verticesA
Current crossing edge-
Selected edges0/5
MST weight0
1 / 12

Correctness and implementation choices

The cut property makes each lightest crossing edge safe. A binary heap implementation runs in O(E log V) on adjacency lists, while a simple dense-graph implementation can run in O(V^2). The visualization scans a compact fixed edge set so every choice stays visible.

Invariant: selected edges form one connected tree, and every selected edge is safe for a minimum spanning tree.

See the same objective approached from a forest in Kruskal's algorithm.