# Minimum Spanning Tree (Kruskal / Prim)

MST with both textbook algorithms: Kruskal's sorted accept/cycle-reject log and Prim's component growth, cross-checked to agree on the total weight; disconnected graphs rejected.

> Canonical page: https://elysiatools.com/en/tools/minimum-spanning-tree

- **Category:** Math & Numbers

- **Keywords:** minimum spanning tree, mst, kruskal, prim, union-find, greedy algorithm, graph, network design, spanning tree, discrete math

## Overview

The Minimum Spanning Tree calculator determines the optimal subset of edges that connects all vertices in an undirected weighted graph with the minimum possible total weight. It supports both Kruskal's algorithm (using edge sorting and cycle detection via union-find) and Prim's algorithm (growing a connected component from an optional start node), verifying total weight consistency and rejecting disconnected graphs.

## Inputs

- **Edges (one per line: node1, node2, weight)** (textarea): One undirected edge per line: two node names (1–8 letters/digits) and a weight (negatives allowed).
- **Algorithm** (select)
- **Start node (Prim only, optional)** (text): e.g. D
- **Decimal Places** (number)

## When to use

- You need to design a cost-efficient physical or logical network connecting multiple nodes without redundant loops.
- You are studying or teaching discrete mathematics and need a step-by-step trace of edge additions and cycle rejections.
- You want to compare the execution sequence of Kruskal's and Prim's algorithms on identical weighted graphs.

## How it works

- Enter undirected weighted edges line by line in the format: node1 node2 weight (e.g., A B 4).
- Select your preferred algorithm (Kruskal or Prim) and specify an optional starting node for Prim's algorithm.
- Set the desired decimal precision for the edge weights and total weight summation.
- The tool parses the graph, skips self-loops, checks for global connectivity, and outputs the detailed step-by-step edge selection log, final edge list, and total spanning tree weight.

## Use cases

- Optimizing fiber-optic, pipeline, or electrical grid layouts to connect all facilities at minimal construction cost.
- Verifying homework assignments and academic graph theory problems step-by-step for Kruskal and Prim algorithms.
- Clustering and distance-based graph reduction in computational geometry and spatial analysis.

## Frequently asked questions

### What edge format does the calculator accept?

Enter one undirected edge per line consisting of two alphanumeric node identifiers (1–8 characters) and a numeric weight, separated by spaces.

### Are negative edge weights allowed?

Yes, both Kruskal's and Prim's algorithms work correctly with negative edge weights in undirected graphs.

### What happens if the input graph is disconnected?

The calculator rejects disconnected graphs because a spanning tree requires all nodes to be in a single connected component.

### Why do Kruskal's and Prim's algorithms produce different edge sequences?

Kruskal's algorithm greedily considers globally lowest-weight edges first across the entire graph, while Prim's algorithm expands outward from an initial node by choosing the lowest-weight boundary edge at each step.

### How are self-loops handled?

Self-loops (edges connecting a node to itself) are automatically skipped since they create immediate cycles and cannot be part of an MST.

## Related tools

- [Density Calculator (ρ = m/V)](https://elysiatools.com/en/tools/density-calculator): Compute density, mass, or volume from the other two, with specific gravity and a float/sink check
- [Pump NPSH (Net Positive Suction Head) Calculator & Cavitation Check](https://elysiatools.com/en/tools/pump-npsh-calculator): Compute the available Net Positive Suction Head (NPSH_a) of a pump and compare it against the required NPSH (NPSH_r) from the pump curve. Head-balance form: NPSH_a = (p_surface_abs - p_vapor) / (ρ·g) + H_static - h_friction. Surface and vapor pressures are absolute; H_static is positive for flooded suction, negative for suction lift. Returns margin (NPSH_a - NPSH_r), ratio (NPSH_a/NPSH_r) and a classification: safe, marginal (margin < 0.5 m), or cavitation likely. If NPSH_r = 0, only NPSH_a is reported. Pressure in Pa/kPa/bar/atm/psi, length in m/ft, density in kg/m³/g/cm³/lb/ft³.
- [Words to Number](https://elysiatools.com/en/tools/words-to-number): Convert English number-words into digits. Handles magnitudes, "and", decimals via "point", and hyphens, replacing the number-run in place.
- [Adaptive 12-Point Hidden Watermark](https://elysiatools.com/en/tools/adaptive-12-point-hidden-watermark): Add a subtle text watermark to one image or every supported image in a ZIP, at all, random, or chosen perimeter positions with automatic dark/light local contrast.
- [Fractional Excretion of Sodium (FENa)](https://elysiatools.com/en/tools/fractional-excretion-sodium): Calculate the Fractional Excretion of Sodium (FENa) to differentiate prerenal from intrinsic acute kidney injury: FENa (%) = \[U_Na × S_Cr\] / \[S_Na × U_Cr\] × 100. In oliguric AKI, FENa <1% suggests prerenal azotemia (sodium-avid state: volume depletion, heart failure, hepatorenal syndrome), while FENa ≥1% suggests intrinsic injury (typically ATN). FENa >4% is sometimes cited as supportive of post-obstructive pathology. Caveats: unreliable on diuretics (use FEUrea <35%), contrast/sepsis ATN can present with low FENa, chronic CKD and glucosuria elevate FENa independently. Derived from Espinel CH, JAMA 1976. Most useful in oliguric AKI; interpret with full clinical context. Not medical advice.
- [Twitter / X Thread Splitter](https://elysiatools.com/en/tools/twitter-thread-splitter): Paste a long text and split it into a numbered X thread that respects the 280-character limit. Splits on word/sentence/paragraph boundaries, auto-adds 1/N numbering, weighs CJK and full-width characters correctly, counts URLs as 23 characters, and shows a live X-style preview card for each tweet with a character meter.
- [AHU Coil Capacity Calculator (Cooling / Heating)](https://elysiatools.com/en/tools/ahu-capacity-calculator): Compute the total, sensible, and latent capacity of an air-handling-unit (AHU) coil from the entering/leaving air state and the dry-air mass flow ṁ_da. Total capacity Qt = ṁ_da·(h1 − h2); sensible capacity Qs = ṁ_da·cp_ma·(T1 − T2) with cp_ma ≈ 1.006 + 1.86·W \[kJ/(kg da·K)\]; latent capacity Ql = Qt − Qs; Sensible Heat Ratio SHR = Qs / Qt. Each state is described by dry-bulb T plus one humidity input (relative humidity φ, or humidity ratio W); W is derived from the Magnus saturation fit when RH is supplied, and enthalpy h = 1.006·T + W·(2501 + 1.86·T) \[kJ/kg da\]. Signed result — works for cooling or heating coils.
- [Buoyancy Calculator (Archimedes, F = ρ·V·g)](https://elysiatools.com/en/tools/buoyancy-calculator): Compute buoyant force, fluid density, or displaced volume from any two, with optional float/sink analysis

## Samples

- [Web Image Processing Python Samples](https://elysiatools.com/en/samples/web-image-processing-python): Web Python image processing examples using PIL/Pillow including reading, saving, resizing, and format conversion
- [SVG Samples](https://elysiatools.com/en/samples/svg-samples): Scalable Vector Graphics (SVG) samples demonstrating various SVG features and techniques
- [Android Image Processing Java Samples](https://elysiatools.com/en/samples/android-image-processing-java): Android Java image processing examples including reading/saving images, scaling, and format conversion
- [Android Image Processing Kotlin Samples](https://elysiatools.com/en/samples/android-image-processing-kotlin): Android Kotlin image processing examples including reading/saving images, scaling, and format conversion