Minimum Spanning Tree (MST) Algorithms

About

A Minimum Spanning Tree (MST) is a subset of the edges of a connected, weighted graph that connects all vertices with the minimum possible total edge weight and without forming any cycles.

A spanning tree of a graph G(V, E) is a tree that:

  • Includes all V vertices of the graph.

  • Contains exactly V-1 edges (since a tree with V nodes has V-1 edges).

  • Does not contain any cycles.

A Minimum Spanning Tree (MST) is a spanning tree where the sum of the edge weights is minimum among all possible spanning trees.

Properties of MST

  1. A graph can have multiple MSTs, but all MSTs will have the same total weight.

  2. If all edge weights are distinct, there will be a unique MST.

  3. If an edge is the smallest edge in a cycle, it must be included in the MST (this is called the cut property).

  4. If an edge is the largest edge in a cycle, it cannot be part of any MST.

  5. The MST of a connected graph is unique if the edge weights are distinct.

Example Graph

     (A)
    /   \
   1      3
  /        \
 (B)--- 2 --(C)
   \        /
    4      5
     \   /
      (D)

Possible MST (one of them):

     (A)
    /   \
   1     3
  /       \
 (B)     (C)
   \
    4
     \
     (D)

Total MST Weight = 1 + 3 + 4 = 8

MST Algorithms

There are two main algorithms to find the MST:

  • Kruskal’s Algorithm (Greedy approach using sorting and Union-Find).

  • Prim’s Algorithm (Greedy approach using priority queue).

Kruskal’s Algorithm

About

Kruskal’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph. It selects edges in increasing order of weight while ensuring that no cycles are formed. It is particularly efficient for sparse graphs (graphs with fewer edges). The algorithm is based on the greedy approach, where the best local decision (selecting the smallest edge) leads to a globally optimal solution (Minimum Spanning Tree).

  • Greedy Nature – It picks the smallest edge first and grows the MST gradually.

  • Cycle Avoidance – It ensures no cycles are formed while adding edges.

  • Uses Disjoint Set Union (DSU) – Also known as Union-Find to detect cycles efficiently.

  • Works on Edge List – The algorithm sorts edges by weight and processes them one by one.

  • Optimal for Sparse Graphs – Performs efficiently when the number of edges E is much smaller than the number of vertices V.

Working of Kruskal’s Algorithm

The algorithm follows these steps:

Step 1: Sort Edges

  • Sort all edges of the graph in ascending order of their weights.

Step 2: Initialize Disjoint Sets

  • Assign each vertex as an individual disjoint set (each vertex is its own component).

Step 3: Process Edges

  • Iterate through the sorted edge list.

  • Include the edge in the MST if it does not form a cycle (use Union-Find for cycle detection).

Step 4: Repeat Until MST is Formed

  • Stop when V-1 edges have been included in the MST (where V is the number of vertices).

Time Complexity Analysis

  • Sorting edges: O(Elog⁡E)O(E \log E)O(ElogE) (using efficient sorting algorithms like Merge Sort or Quick Sort).

  • Union-Find operations (with path compression & union by rank): O(Eα(V)), where 𝛼 ( 𝑉 ) is the inverse Ackermann function, which grows very slowly and is nearly constant for practical inputs.

  • Total Complexity: O(Elog⁡E), which is efficient for sparse graphs.

Example of Kruskal’s Algorithm

Graph Representation

Consider the following weighted graph:

      2
  A ------- B
  |  \    / |
  |   \  /  |
 4|    C    |3
  |   /  \  |
  |  /    \ |
  D ------- E
      1

Step 1: Sort the Edges by Weight

Edge
Weight

D–E

1

A–B

2

B–E

3

A–D

4

B–C

4

C–E

5

Step 2: Initialize Each Vertex as a Separate Set

Initially, each vertex (A, B, C, D, E) is its own component.

Step 3: Pick the Smallest Edge That Doesn't Form a Cycle

  1. Include D–E (1) → No cycle, add to MST.

  2. Include A–B (2) → No cycle, add to MST.

  3. Include B–E (3) → No cycle, add to MST.

  4. Include A–D (4) → No cycle, add to MST.

  5. Stop (MST contains 4 edges for 5 vertices).

Final MST

      2
  A ------- B
  |         |
 4|         |3
  |         |
  D ------- E
      1

Total MST Weight = 1 + 2 + 3 + 4 = 10

Cycle Detection Using Union-Find

To ensure that adding an edge does not form a cycle, we use the Union-Find (Disjoint Set) data structure with two operations:

  1. Find() – Determines the root representative of a set (uses path compression for efficiency).

  2. Union() – Merges two sets based on rank to keep the tree shallow.

If two vertices of an edge belong to the same set, adding the edge would form a cycle, so it is skipped.

Prim’s Algorithm

About

Prim’s Algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted, and undirected graph. Unlike Kruskal’s Algorithm, which works edge-by-edge, Prim’s Algorithm grows the MST vertex-by-vertex, always adding the minimum-weight edge that connects a new vertex to the MST.

It is particularly efficient for dense graphs (graphs with many edges). The algorithm is based on the greedy approach, where local optimal choices (picking the smallest edge) lead to a globally optimal solution (MST).

  • Greedy Nature – It always selects the minimum-weight edge from the vertices already in the MST.

  • Vertex-Based Expansion – The MST starts from one vertex and grows by adding one vertex at a time.

  • No Cycle Formation – The algorithm never forms a cycle because it only considers edges that connect an MST vertex to a non-MST vertex.

  • Efficient with Priority Queues – Implemented using a Min Heap (Priority Queue) for efficiency.

  • Best for Dense Graphs – Performs better when E is close to V².

Working of Prim’s Algorithm

The algorithm follows these steps:

Step 1: Select an Initial Vertex

  • Start from any random vertex (commonly vertex 0).

  • Mark it as part of the MST.

Step 2: Grow the MST

  • Among all edges that connect a vertex in the MST to a vertex outside the MST, pick the smallest one.

  • Add the new vertex to the MST.

Step 3: Repeat Until MST is Formed

  • Repeat until V-1 edges have been added to the MST (where V is the number of vertices).

Time Complexity Analysis

  • Using an adjacency matrix (without a priority queue): O(V^2).

  • Using a Min Heap (Priority Queue) with an adjacency list: O(Elog⁡V), where E is the number of edges and V is the number of vertices.

Example of Prim’s Algorithm

Graph Representation

Consider the following weighted graph:

        (A)
     2 /   \ 3
      /     \
     B ----- C
     |  \   /
    4|   \ /5
     |    D
     \   /
      1
     (E)

Step 1: Select an Initial Vertex

Let's start with vertex A.

Step 2: Select the Smallest Edge Connected to MST

Step
Chosen Edge
Weight
MST Set

1

A → B

2

{A, B}

2

A → C

3

{A, B, C}

3

C → D

5

{A, B, C, D}

4

D → E

1

{A, B, C, D, E}

Final MST

        (A)
     2 /   \ 3
      /     \
     B       C
      \     /
       \   /
        (D)
         |
         1
        (E)

Total MST Weight = 2 + 3 + 5 + 1 = 11

Implementation Details

Prim’s Algorithm is efficiently implemented using a Min Heap (Priority Queue):

  • Maintain a Min Heap of edges that connect the MST to non-MST vertices.

  • Extract the smallest edge at each step.

  • Update the heap with new edges connecting the newly added vertex.

This results in an efficient implementation with O(E log V) time complexity.

Comparison of Prim’s with Kruskal’s Algorithm

Feature
Prim’s Algorithm
Kruskal’s Algorithm

Approach

Vertex-based

Edge-based

Best for

Dense Graphs (E is close to V²)

Sparse Graphs (E << V²)

Complexity

O(Elog⁡V) with Min Heap

O(Elog⁡E)

Data Structure

Priority Queue (Min Heap)

Edge List + Union-Find

Edge Sorting

Not Required

Required

How it Grows

Expands from one vertex

Picks the lightest edge

Applications of MST

  • Network Design: Used in designing network topologies, including computer networks, telecommunication networks, and power grids to minimize wiring costs.

  • Clustering and Image Segmentation: Used in clustering algorithms like Kruskal’s Clustering Algorithm in machine learning. Used in image segmentation for grouping pixels based on similarity.

  • Approximation Algorithms: Used in approximate solutions for problems like Traveling Salesman Problem (TSP).

  • Circuit Design: Used in circuit board design to minimize wiring and avoid redundant paths.

  • Road and Railway Construction: Used in urban planning to minimize the cost of road, railway, or pipeline construction.

PreviousShortest Path AlgorithmsNextDynamic Programming

Last updated

Was this helpful?