Kruskal’s algorithm
Sort edges by weight. Accept the next lightest edge only when it joins two different components; otherwise reject it because it would close a cycle.
Minimum Spanning Tree Calculator — Kruskal and Prim Visualizer
Enter an undirected weighted graph
Kruskal considers edges globally from lowest to highest weight.
Used only by Prim. Leave blank to start at the first listed vertex.
Separate labels with commas, semicolons, or lines. Include isolated vertices here.
Private by design: your graph is parsed and calculated on this device. It is not uploaded, stored, or included in the page URL.
Available edgeAcceptedCurrent edgeRejected now
Step 0 of 0
ReadyCalculate a graph to inspect the algorithm.
| Step | Edge | Decision | Weight | Running total |
|---|---|---|---|---|
| No calculation yet. | ||||
Advertisement
How Kruskal’s and Prim’s algorithms find an MST
A spanning tree connects all vertices of a connected undirected graph without a cycle. Every spanning tree on V vertices has exactly V − 1 edges. A minimum spanning tree (MST) minimizes the sum of those edge weights.
Prim’s algorithm
Start at one vertex. Repeatedly accept the lightest edge crossing from the growing tree to an unvisited vertex.
Objective
minimize Σ w(e)
subject to: connected and acyclic
This visualizer uses disjoint sets for Kruskal and an edge frontier for Prim. With sorting and the small browser-oriented limits here, both implementations run in O(E log E) time; memory use is O(V + E).
Worked minimum spanning tree example
For the sample graph, both algorithms find total weight 13. One minimum spanning tree contains B–C (1), A–C (2), D–E (2), E–F (3), and B–D (5). The sum is 1 + 2 + 2 + 3 + 5 = 13.
| Kruskal candidate | Decision | Reason |
|---|---|---|
| B–C (1) | Accept | Joins two separate components. |
| A–C (2) | Accept | Adds A to the B–C component. |
| D–E (2) | Accept | Joins D and E. |
| E–F (3) | Accept | Adds F to the D–E component. |
| A–B (4) | Reject | A and B are already connected; this would create a cycle. |
| B–D (5) | Accept | Joins the two remaining components. |
Input rules, assumptions, and limits
Weighted edge format
Enter one undirected edge per line as first,second,weight, for example A,B,4.5. Endpoint labels are case-sensitive.
Disconnected graphs
A disconnected graph has no spanning tree. The calculator still returns a minimum spanning forest and reports its component count. Prim restarts at the next unvisited vertex.
Duplicates and ties
For a repeated undirected pair, the smallest supplied weight is kept. Equal weights are broken deterministically by input order. Ties can produce more than one valid MST.
Numerical limits
Weights must be finite numbers from −1 trillion through 1 trillion. The tool accepts up to 60 vertices and 2,000 unique edges and displays up to six decimal places.
Assumptions: the graph is finite, undirected, and weighted. Self-loops are rejected because they cannot help connect components. Negative and zero weights are valid for minimum spanning trees.
Definitions and algorithm behavior follow NIST’s Dictionary of Algorithms and Data Structures and OpenStax’s treatment of Kruskal’s and Prim’s algorithms.
Calculation note: connected, disconnected, negative-weight, zero-weight, decimal-weight, duplicate-edge, tied-weight, isolated-vertex, single-vertex, and invalid-input cases checked by the Starlight Tools editorial team. Last reviewed: .
Minimum spanning tree calculator FAQ
What is a minimum spanning tree?
A minimum spanning tree is an acyclic set of edges that connects every vertex of a connected undirected weighted graph with the smallest possible total edge weight. A graph with V vertices has V − 1 edges in any spanning tree.
What is the difference between Kruskal’s and Prim’s algorithms?
Kruskal considers all edges from lowest to highest weight and accepts one when it joins different components. Prim starts at one vertex and repeatedly adds the lightest edge from the growing tree to an unvisited vertex.
Do Kruskal and Prim always return the same tree?
They return the same minimum total weight on a connected graph, but equal edge weights can allow several different MSTs, so their selected edge sets may differ.
What happens if the graph is disconnected?
No spanning tree can connect it. The calculator reports a minimum spanning forest: one minimum tree for each connected component.
Can an MST have negative or zero edge weights?
Yes. Both algorithms work with finite negative, zero, or positive weights. Unlike Dijkstra’s shortest-path algorithm, they do not require non-negative weights.
Does Prim’s starting vertex change the answer?
It does not change the minimum total weight, but it can change the selected tree and step order when multiple MSTs exist.
Why are self-loops rejected?
A self-loop connects a vertex to itself and cannot join two components, so it can never belong to a spanning tree.
Does the calculator save my graph?
No. Parsing, calculation, visualization, copying, and CSV creation happen locally in your browser. The tool does not transmit or store the graph input.