Minimum Spanning Tree (Kruskal / Prim)

Minimum Spanning Tree (Kruskal / Prim) | Online Free Tool | Elysia Tools

Tool usage guide

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Category: Math & Numbers
Input types: textarea, select, text, number
Output type: text
Sample coverage: 4
API ready: Yes

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.

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

1Enter undirected weighted edges line by line in the format: node1 node2 weight (e.g., A B 4).
2Select your preferred algorithm (Kruskal or Prim) and specify an optional starting node for Prim's algorithm.
3Set the desired decimal precision for the edge weights and total weight summation.
4The 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.

Examples

1. Finding MST via Kruskal's Algorithm

Computer Science Student

Background

A student needs to solve a discrete math problem to find the minimum spanning tree of a 6-node network and identify which edge gets rejected for creating a cycle.

Problem

Determine the step-by-step edge acceptance/rejection order and calculate the total weight using Kruskal's algorithm.

How to use

Paste the 8 edge definitions into the Edges field, select 'Kruskal (sort + union-find)' as the algorithm, set decimal places to 2, and run the calculation.

edges: A B 4\nA C 2\nB C 5\nB D 10\nC E 3\nD E 4\nD F 11\nE F 8
algorithm: kruskal
decimalPlaces: 2

Outcome

Edges A—C (2), C—E (3), A—B (4), D—E (4), and E—F (8) are accepted, edge B—C (5) is rejected as a cycle, yielding a total MST weight of 21 across 5 edges.

2. Network Expansion with Prim's Algorithm

Network Engineer

Background

An infrastructure engineer wants to plan a cable route starting specifically from a primary server node 'D' across 6 regional access points.

Problem

Calculate the component growth sequence and optimal spanning tree starting from node D.

FAQ

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.

edges: A B 4\nA C 2\nB C 5\nB D 10\nC E 3\nD E 4\nD F 11\nE F 8
algorithm: prim
startNode: D
decimalPlaces: 2

Run this tool

Examples that match this tool

Continue with connected tools and hubs

Learn when to use this tool, what it supports, and how real users apply it.

Key facts

Overview

When to use

How it works

Use cases

Examples

1. Finding MST via Kruskal's Algorithm

2. Network Expansion with Prim's Algorithm

FAQ

Web Image Processing Python Samples

SVG Samples

Android Image Processing Java Samples

Android Image Processing Kotlin Samples

Density Calculator (ρ = m/V)

Pump NPSH (Net Positive Suction Head) Calculator & Cavitation Check

Words to Number

Adaptive 12-Point Hidden Watermark