Kruskal's vs Prim's Algorithm

Compare Kruskal's vs Prim's algorithms for Minimum Spanning Tree.

Min Cost to Connect All Points

Given 2D points, connect all points such that total Manhattan distance is minimized.

Redundant Connection (Cycle in Undirected Graph)

Return an edge that can be removed so that the resulting graph is a tree of N nodes.

Graph Algorithms & TraversalsAdvanced LevelStudy Time: 28 mins

Kruskal's MST Algorithm

Kruskal's Algorithm finds the Minimum Spanning Tree (MST) of a connected weighted graph by sorting all edges by weight and adding them using Union-Find cycle detection.

Kruskal's Minimum Spanning Tree (MST)

Graph loaded. Click Find MST to sort edges and build the Minimum Spanning Tree.

MST Total Cost:-

Speed:

Sorted Edges Checklist

C - D (weight: 1)Pending

A - C (weight: 2)Pending

D - E (weight: 2)Pending

B - C (weight: 3)Pending

A - B (weight: 4)Pending

C - E (weight: 5)Pending

B - E (weight: 6)Pending

Real-world analogy: Connecting Power Grids

Union-Find (DSU)

Hover over items for details

Connect 10 towns with electric cables. Sort all possible cable costs and lay down the cheapest cables first, skipping any cable that creates an electrical loop.

Union-Find (DSU)= Detects graph cycles in near-O(1) time using path compression.

Complexity analysis

Scenario Simulator: Dataset Size (N = 500)

Presets:

N = 10N = 10,000

Complexity Curve MapKruskal's MST: O((V + E) log V) Time

Hover curves to inspect classes

Time Steps (N=500)

~4,483 steps (Linearithmic)

O((V + E) log V) Time

Space Footprint

O(V + E) Graph Memory

Memory growth rate as N expands.

Performance Rank

Moderate Tier

Relative efficiency rating for large N.

Operation	Time Complexity	Space Complexity
Kruskal MST Time	O(E log E)	O(V + E)

Code implementations

function kruskal(numVertices, edges) {
  edges.sort((a, b) => a.weight - b.weight);
  const dsu = new DisjointSet(numVertices);
  const mst = [];
  for (const edge of edges) {
    if (dsu.union(edge.u, edge.v)) mst.push(edge);
  }
  return mst;
}