How Kruskal's algorithm works

Given a connected, weighted, undirected graph \( G = (V, E) \), a minimum spanning tree (MST) is a subset of edges \( T \subseteq E \) that:

• connects all vertices,
• contains exactly \(|V| - 1\) edges, and
• has minimum possible total weight among all such spanning trees.

Kruskal's algorithm builds an MST by repeatedly adding the cheapest edge that does not create a cycle, using a disjoint-set union (DSU) / union–find data structure to track components efficiently.

// Input: Weighted undirected graph G = (V, E)
KruskalMST(V, E):
  // sort edges by non-decreasing weight
  sort E by weight ascending

  make-set(v) for each v in V   // DSU initialization
  MST = empty set

  for each edge (u, v, w) in E (in sorted order):
    if find-set(u) != find-set(v):    // different components?
      MST.add((u, v, w))              // safe to add
      union(u, v)                     // merge components

  return MST

The union–find structure supports almost-constant-time find and union operations, so the overall time complexity is dominated by sorting the edges:

• \(O(|E|\log|E|)\) for sorting the edges,
• plus near-linear time for the union–find operations.

Worked example

Consider the sample graph with vertices \( \{A, B, C, D, E, F, G, H, I\} \) and edges such as:

A B 4
A H 8
B H 11
B C 8
C D 7
C F 4
C I 2
D E 9
D F 14
E F 10
F G 2
G H 1
G I 6
H I 7

When you click Compute MST, the calculator sorts all edges by weight (starting with G H 1, C I 2, F G 2, …) and adds each edge if it does not connect vertices that are already in the same component. The step-by-step table shows exactly which edges were added or skipped.

Interpreting the results

• If the number of selected edges equals \(|V| - 1\), the graph is connected and the result is a valid minimum spanning tree.
• If fewer edges are selected, the graph is disconnected and the result is a minimum spanning forest (one MST per connected component).
• The total weight is the sum of the weights of all edges in the MST (or forest).

How to use the Kruskal's Algorithm Calculator

1. List your edges. For each undirected edge, choose a pair of vertex labels (e.g. A and B) and a weight.
2. Enter one edge per line. Use the format u v w, for example A B 7 or 1,2,3.5.
3. (Optional) Provide a vertex set. If your graph contains isolated vertices, list them in the “Known vertices” field, separated by commas.
4. Click “Compute MST”. The tool applies Kruskal's algorithm and shows both a concise summary and detailed steps.
5. Review connectivity. Check whether the graph is fully connected or if you obtained a minimum spanning forest.

Limitations and notes

• The calculator expects a finite, undirected graph with real-valued weights. Directed graphs and negative cycles are out of scope.
• If multiple MSTs have the same total weight, Kruskal's algorithm may return any one of them depending on the tie-breaking order of edges.
• For very large graphs, performance is mainly limited by your browser and device resources.

FAQ – Kruskal's Algorithm & MST