Kruskal vs Prim Visualizer

Compare Kruskal's and Prim's minimum spanning tree strategies through animated edge choices, costs, and cycle prevention.

Ready. Use the controls to begin exploring Kruskal's & Prim's.

Kruskal's Vs. Prim's Algorithm

Minimum Spanning Tree Comparison

Click any node to set Prim's start node

Prim Start:A

Speed: 600ms

Kruskal's Algorithm

Total Weight: 0

Edges Accepted

Prim's Algorithm

Total Weight: 0

Edges Accepted

Kruskal's Algorithm

Sorts every edge by weight and greedily accepts the cheapest one that doesn't create a cycle, using a union-find structure to detect cycles in near-constant time.

Data Structure: Union-Find (Disjoint Set)
Visual Pattern: Edges lighting up out of order across the whole graph.
Best For: Sparse graphs, edge lists.

Prim's Algorithm

Grows a single tree from a start node, at each step attaching the cheapest edge that connects the tree to a new node.

Data Structure: Priority Queue / Min-Heap
Visual Pattern: A single connected blob expanding outward.
Best For: Dense graphs, adjacency lists.

Kruskal's & Prim's Algorithm Complete Info Card

Minimum Spanning TreeGreedy Algorithm

Both algorithms build a Minimum Spanning Tree - the cheapest set of edges connecting every node with no cycles - but they make their greedy choice from two different vantage points: globally (Kruskal) versus locally from a growing tree (Prim).

Kruskal's Characteristics

Time Complexity

Dominated by sorting the edges

O(E log E)

Space Complexity

Union-Find structure plus edge list

O(V + E)

Data Structure

Detects cycles in near-constant time

Union-Find

Best Graph Type

Edge-list-driven, scales with E

Sparse

Prim's Characteristics

Time Complexity

Using a binary heap priority queue

O(E log V)

Space Complexity

Visited set plus adjacency list

O(V + E)

Data Structure

Always pops the cheapest frontier edge

Priority Queue

Best Graph Type

Adjacency-list-driven, scales with V

Dense

Algorithm Comparison

Aspect	Kruskal	Prim
Growth Pattern	Multiple components merge over time	Single tree grows outward
Cycle Check	Union-Find (find/union)	Implicit - only unvisited nodes considered
Edge Order	Globally sorted by weight	Locally cheapest from the tree's frontier
Starting Point	None needed	Requires a starting node
Typical Use	Sparse graphs, edge lists	Dense graphs, adjacency matrices

When to Use Which

•Sparse graph with a ready-made edge list → Kruskal
•Dense graph stored as an adjacency matrix → Prim
•Need to grow a network incrementally from one site → Prim

Common Pitfalls

•Forgetting union-find path compression slows Kruskal down
•Both fail silently on disconnected graphs - check component count first
•Neither works directly on directed graphs

Did You Know? Both algorithms always produce a minimum spanning tree of the same total weight for a given graph, even though they build it up in completely different orders.

MSTUnion-FindNetwork design