Minimum Spanning Tree Finder

Find minimum spanning trees for weighted graphs using Prim's or Kruskal's algorithm. Visualize graphs and MSTs with interactive tools.

Minimum Spanning Tree (MST): A subset of edges that connects all vertices with the minimum total edge weight, without forming cycles.

Prim's algorithm starts with a single vertex and grows the MST by adding the cheapest edge from the tree to a vertex not yet in the tree.
5 vertices
Enter edge weights. Leave diagonal as 0 (no self-loops).
Simple Graph (5 vertices)
Complete Graph (6 vertices)
Sparse Graph (7 vertices)
Complex Graph (8 vertices)
Calculating Minimum Spanning Tree...

Understanding Minimum Spanning Trees

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Formal Definition:

Given a connected, undirected graph G = (V, E) with weight function w: E → ℝ, a minimum spanning tree T = (V, E') where E' ⊆ E such that:

  1. T connects all vertices in V
  2. T has no cycles
  3. The sum of weights Σe∈E' w(e) is minimized

Prim's Algorithm

1

Initialization: Start with an arbitrary vertex as the initial MST. Initialize a set to track visited vertices.

2

Greedy Selection: Repeatedly add the cheapest edge that connects a vertex in the MST to a vertex not yet in the MST.

3

Termination: Continue until all vertices are included in the MST.

Time Complexity: O(E log V) using a binary heap, where V is vertices and E is edges.

Kruskal's Algorithm

1

Sort Edges: Sort all edges in non-decreasing order of their weight.

2

Initialize Forest: Start with each vertex as a separate tree (using disjoint-set data structure).

3

Greedy Selection: Iterate through sorted edges, adding an edge to the MST if it doesn't form a cycle (connects different trees).

4

Termination: Stop when V-1 edges have been added to the MST.

Time Complexity: O(E log E) or O(E log V) using union-find with path compression.

Applications of Minimum Spanning Trees

  • Network Design: Designing least-cost networks for telephone, electrical, hydraulic, or computer networks
  • Transportation Networks: Planning roads, railways, or airline routes with minimum construction costs
  • Cluster Analysis: In data mining and machine learning for hierarchical clustering
  • Image Segmentation: In computer vision for partitioning images into regions
  • Circuit Design: Connecting pins on a chip with minimum wire length
  • Approximation Algorithms: For NP-hard problems like the traveling salesman problem

Key Properties:

  • Cut Property: For any cut of the graph, the minimum weight edge crossing the cut is in the MST
  • Cycle Property: For any cycle in the graph, the maximum weight edge is not in the MST
  • Uniqueness: If all edge weights are distinct, the MST is unique
  • Number of Edges: An MST always has V-1 edges for a graph with V vertices

Frequently Asked Questions

Prim's algorithm grows the MST from an initial vertex, always adding the minimum edge connecting the MST to a new vertex. Kruskal's algorithm sorts all edges and adds them in increasing weight order, skipping edges that would create cycles. Prim's is generally faster for dense graphs, while Kruskal's can be simpler to implement with a disjoint-set data structure.

Yes, if multiple edges have the same weight, there can be multiple MSTs with the same total weight. Both Prim's and Kruskal's algorithms will find an MST, but which one they find depends on implementation details like the order in which edges are considered.

No, standard MST algorithms (Prim's and Kruskal's) only work for undirected graphs. For directed graphs, the equivalent problem is called the minimum spanning arborescence or minimum branching problem, which is solved by different algorithms like Chu-Liu/Edmonds' algorithm.

For a disconnected graph, there is no spanning tree that connects all vertices. Instead, you would find a minimum spanning forest—a collection of minimum spanning trees, one for each connected component of the graph. Both algorithms can be adapted to handle disconnected graphs by applying them to each component separately.

Both Prim's and Kruskal's algorithms are greedy because they make a series of choices, each of which looks best at the moment (the minimum weight edge that doesn't create a cycle). Despite this local optimization approach, they both guarantee finding the globally optimal solution (the MST), which is proven by the cut and cycle properties of MSTs.