Minimum Spanning Tree

Minimum Spanning Tree

Graph connectivity algorithms (Kruskal's and Prim's) that find the minimum cost to link all vertices.

What is Minimum Spanning Tree?

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. Kruskal's Algorithm builds the tree by sorting all edges and adding them one-by-one, using a Disjoint-Set (Union-Find) data structure to prevent cycles.

Key Characteristics:

  • Connects all vertices without loops/cycles.
  • Total edges in MST is always V-1.
  • Prim's is node-centric (good for dense graphs).
  • Kruskal's is edge-centric (good for sparse graphs).

Complexity Analysis

Avg Time Complexity: O(E * log V) using priority queues or sorting
Space Complexity: O(V + E) for storing graph and Union-Find
Best Case: O(E * log V)
Worst Case: O(E * log V)

How it Works Step-by-Step

  1. Sort Edges: Sort all edges in non-decreasing order of their weight.
  2. Union-Find Init: Create a disjoint set representation for each vertex.
  3. Pick Smallest Edge: Select the smallest edge. Check if vertices belong to the same subset.
  4. Include or Skip: If subsets are different, merge subsets (union) and add the edge to the MST. Otherwise, skip.
  5. Terminate: Repeat until V-1 edges are added to the MST.

Code Implementation

Worked Trace Example

Edges: A-B(4), B-C(2), A-C(3). 3 vertices:
1. Sorted edges: B-C(2), A-C(3), A-B(4).
2. Add B-C(2): MST has B-C.
3. Add A-C(3): doesn't make a cycle. MST has B-C, A-C.
4. Edge A-B(4) forms cycle A-C-B-A: discarded.
Result: MST edges: B-C and A-C. Total weight = 5.

Ready to Understand Minimum Spanning Tree Visually?

Don't just read about it. Launch our interactive, premium algorithm visualizer to step through calculations in real-time.

Launch Minimum Spanning Tree Visualizer →