Kruskal's MST

O(E log E)

Kruskal's algorithm builds a minimum spanning tree by sorting all edges by weight and adding them one by one, skipping an edge if its two endpoints are already connected (which would create a cycle). A union-find structure tracks which nodes are connected. It runs in O(E log E), dominated by the sort. Here edge weights are the distances between nodes.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Sort every edge by weight, cheapest first.
  2. Take the next edge; if its endpoints are in different components, add it.
  3. Merge those two components (union-find).
  4. If they're already connected, skip the edge — it would make a cycle.

Pseudocode

1kruskal(graph):                     # O(E log E)2  sort all edges by weight3  for each edge (u, v) in order:4    if find(u) ≠ find(v):            # different components5      union(u, v); add the edge to the MST6    else: skip it (it would make a cycle)