Kruskal’s Algorithm Calculator – Minimum Spanning Tree Visualizer

How this Kruskal’s algorithm calculator works

This tool implements Kruskal’s algorithm to find a minimum spanning tree (MST) of a weighted undirected graph. It uses a union–find (disjoint-set) data structure with path compression and union by rank to detect cycles efficiently.

1. Building the graph

• Add vertices by typing a label (A, B, 1, etc.) or clicking on the canvas.
• Add edges by:
  • Typing endpoints and weight in the “Add edge” form, or
  • Clicking two vertices on the canvas and entering a weight.
• The graph is treated as simple and undirected: parallel edges are allowed, but self-loops are ignored by Kruskal’s algorithm.

2. Kruskal’s algorithm steps

Input: Graph G = (V, E) with edge weights w(e)
Output: Minimum spanning tree T

1. Sort all edges E in non-decreasing order of weight.
2. Initialize T ← ∅.
3. Initialize a disjoint-set (union–find) structure over V.
4. For each edge e = (u, v) in sorted order:
     a. If find(u) ≠ find(v):   // u and v are in different components
          - Add e to T
          - Union(u, v)
        Else:
          - Skip e (it would create a cycle)
5. Return T.

In this calculator you can:

• See the sorted edge list and which edge is currently being processed.
• Step forwards and backwards through the algorithm.
• See edges colored by status:
  • Green: edge is in the MST.
  • Red: edge rejected because it would create a cycle.
  • Gray: not yet processed.

3. Time complexity

Let \(V\) be the number of vertices and \(E\) the number of edges.

• Sorting edges: \(O(E \log E)\).
• Union–find operations: almost \(O(1)\) amortized per edge.

Overall time complexity is:

4. Minimum spanning tree vs. minimum spanning forest

If the graph is connected, Kruskal’s algorithm returns a single MST that spans all vertices. If the graph is disconnected, the algorithm still works but produces a minimum spanning forest (an MST for each connected component). The summary box will warn you when the graph is not fully connected.

5. When to use Kruskal’s algorithm

• Graphs with many edges but few vertices (sparse graphs).
• When edges are naturally stored in a list (e.g., network links, roads).
• When you want a clean step-by-step explanation of MST construction.

Worked example

Load the built-in example to see a typical run:

1. Click “Load example”.
2. Click “Run Kruskal”.
3. Use “Next step” to walk through each edge decision.

Observe how the total MST weight increases only when an edge connects two previously separate components.

FAQ

Can edge weights be negative?

Yes. Kruskal’s algorithm works with negative weights as long as the graph has no negative cycles (which is irrelevant for MSTs because trees are acyclic). The calculator will sort edges by weight, including negative values.

Does the order of vertices matter?

No. Only the set of edges and their weights matters. Vertex labels are used for display and to identify endpoints in the edge list.

How is this different from Prim’s algorithm?

Prim’s algorithm grows the MST from a starting vertex, always adding the cheapest edge that connects the current tree to a new vertex. Kruskal’s algorithm, by contrast, considers edges globally in sorted order and uses union–find to avoid cycles. Both produce an MST, but they have different implementation trade-offs.