FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Minimum Spanning Tree (MST)



Minimum Spanning Tree (MST)

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

The concept of a Minimum Spanning Tree is widely used in computer networks, transportation systems, electrical power distribution, water pipelines and many other engineering applications where the objective is to connect all locations with the minimum possible cost.

Prerequisite Concepts

Concept Description
Graph A collection of vertices connected by edges.
Weighted Graph A graph in which every edge has an associated weight or cost.
Connected Graph Every vertex can be reached from every other vertex.
Tree A connected graph without any cycle.

What is a Spanning Tree?

A Spanning Tree is a tree that connects all the vertices of a connected graph using exactly (V − 1) edges, where V represents the number of vertices in the graph.

A graph may have multiple spanning trees, but only one or more of them will have the minimum total edge weight. Such a spanning tree is known as the Minimum Spanning Tree (MST).

Characteristics of Minimum Spanning Tree

Property Description
No Cycles MST never contains a cycle.
Connected Graph All vertices remain connected.
Minimum Cost Total edge weight is minimum.
Edges Always contains (V − 1) edges.

Illustration


        A

      4 | \ 2

        |  \

        |   \

        B----C

        | \5 |

      6 |  \ |3

        |   \|

        D----E

          1

Minimum Spanning Tree

A ---- C (2)

C ---- E (3)

E ---- D (1)

A ---- B (4)

Total Cost = 10

Figure 1 : Example of a Minimum Spanning Tree

Real-Life Example

Suppose a government wants to connect five villages using roads. Since constructing roads is expensive, the objective is to connect all villages while minimizing the total construction cost. The Minimum Spanning Tree provides the most economical solution by selecting only the necessary roads with the minimum total cost.

Example

Edge Weight
A - B 4
A - C 2
B - C 5
B - D 6
C - E 3
D - E 1

The Minimum Spanning Tree selects the edges having the smallest total weight while ensuring that all vertices remain connected and no cycle is formed.

Properties of Minimum Spanning Tree

Property Description
Connected Every vertex of the graph must remain connected.
No Cycle An MST never contains any cycle.
Minimum Weight The total weight of all selected edges is minimum.
Edges An MST always contains exactly (V − 1) edges.
Unique MST If all edge weights are different, the graph has a unique Minimum Spanning Tree.

How is a Minimum Spanning Tree Constructed?

A Minimum Spanning Tree is constructed by repeatedly selecting the edge having the smallest possible weight while ensuring that no cycle is formed. The process continues until all vertices become connected.

The two most popular algorithms used for constructing a Minimum Spanning Tree are Prim's Algorithm and Kruskal's Algorithm. Both algorithms always attempt to minimize the total cost of connecting all vertices.

Algorithms Used for MST

Algorithm Approach
Prim's Algorithm Expands the tree one vertex at a time by selecting the minimum-weight edge.
Kruskal's Algorithm Selects the smallest edge first while avoiding cycles.

Complexity Overview

Algorithm Time Complexity Suitable For
Prim's Algorithm O(E log V) Dense Graphs
Kruskal's Algorithm O(E log E) Sparse Graphs

Advantages of Minimum Spanning Tree

  • Minimizes the total connection cost.
  • Provides efficient network design.
  • Avoids unnecessary cycles.
  • Ensures all vertices remain connected.
  • Useful for solving real-world optimization problems.

Limitations of Minimum Spanning Tree

  • Applicable only to connected weighted graphs.
  • Does not consider network traffic or reliability.
  • Any change in edge weights may produce a different MST.
  • Cannot be applied directly to disconnected graphs.

Applications of Minimum Spanning Tree

Application Description
Computer Networks Connecting computers using minimum cable cost.
Road Construction Connecting cities using minimum construction cost.
Electric Power Distribution Designing economical transmission networks.
Water Supply Networks Connecting pipelines at minimum installation cost.
Telecommunication Designing low-cost communication networks.

Prim's Algorithm vs Kruskal's Algorithm

Prim's Algorithm Kruskal's Algorithm
Starts from a vertex. Starts from the smallest edge.
Builds one tree. Builds multiple small trees and merges them.
Suitable for dense graphs. Suitable for sparse graphs.
Uses Priority Queue. Uses Sorting and Union-Find.

Important Points

  • A Minimum Spanning Tree connects all vertices with minimum total cost.
  • An MST never contains cycles.
  • An MST always contains exactly (V − 1) edges.
  • Prim's and Kruskal's Algorithms are the two standard algorithms for constructing an MST.
  • Minimum Spanning Trees are widely used in communication and transportation networks.

Exam Tip

AKTU examinations frequently ask students to differentiate between a Graph, a Spanning Tree, and a Minimum Spanning Tree. They also ask for a comparison between Prim's Algorithm and Kruskal's Algorithm. Learn the basic definitions and remember that an MST always contains (V − 1) edges and no cycles.

Summary

A Minimum Spanning Tree (MST) is a spanning tree having the minimum possible total edge weight. It is one of the most important concepts in Graph Theory and Design and Analysis of Algorithms. Prim's Algorithm and Kruskal's Algorithm are the two standard Greedy algorithms used to construct a Minimum Spanning Tree efficiently.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com