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

Kruskal's Minimum Spanning Tree

A global greedy edge order guarded by disjoint sets

Connect every vertex at minimum total cost

A minimum spanning tree connects every vertex of a connected, undirected weighted graph with exactly V - 1 edges, no cycle, and the smallest possible total weight. Kruskal's algorithm builds that tree from a forest of isolated vertices.

Accept the lightest safe edge

Sort all edges by weight. Consider them from lightest to heaviest and accept an edge only when its endpoints belong to different components. A disjoint-set structure answers that connectivity question and merges the two components after an accepted edge.

In the player, amber marks the edge under consideration, green edges belong to the growing tree, and dashed edges were rejected because they would close a cycle. The variable panel keeps the selected edge count and total weight visible throughout the scan.

123456789ABCDEF

Sort all 9 edges by weight; the MST is empty and every vertex starts in its own set.

1function kruskal(edges: [number, number, number][], n: number): number {
2 edges.sort((a, b) => a[2] - b[2]);
3 const parent = Array.from({ length: n }, (_, i) => i);
4 const find = (x: number): number => {
5 while (parent[x] !== x) x = parent[x];
6 return x;
7 };
8 let weight = 0;
9 for (const [u, v, w] of edges) {
10 const ru = find(u), rv = find(v);
11 if (ru === rv) continue;
12 parent[ru] = rv;
13 weight += w;
14 }
15 return weight;
16}
Edges E9
Current edge-
MST edges0/5
MST weight0
Cycle rejections0
1 / 20

Why the greedy choice is safe

The cut property says that a lightest edge crossing any cut is safe for some minimum spanning tree. Each accepted edge joins two current components, so it is a lightest crossing edge for that cut. Sorting costs O(E log E); disjoint-set operations add almost constant amortized work per edge.

Invariant: the accepted edges always form an acyclic forest that can be extended to a minimum spanning tree.

Compare this global edge scan with Prim's vertex-driven growth on the same weighted graph.