Minimum Spanning Tree

Learn about the Minimum Spanning Tree (MST), its properties, applications, and algorithms. Explore Prim’s and Kruskal’s greedy approaches to efficiently connect all vertices in a weighted graph at minimum cost.

Minimum Spanning Tree 

Introduction

A Minimum Spanning Tree (MST) is a spanning tree that connects all vertices in a connected, undirected, and weighted graph with the minimum total edge weight.
It contains no cycles, and every vertex is connected to the tree.

Important Definitions

• Graph: A set of vertices and edges.
• Weighted Graph: A graph in which each edge has a weight.
• Spanning Tree:
  • Connects all vertices.
  • Contains no cycles.
  • Total edges = (V − 1), where V is the number of vertices.

A Minimum Spanning Tree is a spanning tree with the lowest total edge weight.

Properties of Minimum Spanning Trees

• MSTs are only possible for connected graphs.
• MSTs contain no cycles.
• If a graph has V vertices, the MST will have V − 1 edges.
• Multiple MSTs are possible if the total edge weights are equal.
• Removing any edge from an MST disconnects the graph.

Applications of Minimum Spanning Trees

MSTs have practical applications in many real-world problems:

• Designing computer networks.
• Planning road and railway networks.
• Electrical wiring and circuit design.
• Water pipelines and cable laying.
• Data clustering and image processing.

Algorithms for Minimum Spanning Trees

Two popular algorithms are commonly used to find MSTs:

1. Prim’s Algorithm
2. Kruskal’s Algorithm

Both algorithms are based on the Greedy Design Technique.

Prim’s Algorithm

Idea:
Prim’s Algorithm starts from a single vertex and gradually grows the MST. At each step, it selects the edge with the lowest weight that connects a new vertex to the tree.

Steps:

1. Start at any vertex.
2. Select the edge with the lowest weight that connects the tree to a new vertex.
3. Add the edge and the vertex to the MST.
4. Repeat until all vertices are connected.

Time Complexity:

• Using an adjacency matrix → O(n²)
• Using a priority queue → O(E log V)

Kruskal’s Algorithm

Idea:
Kruskal’s Algorithm sorts all edges by weight and then adds the smallest edge to the MST, provided it does not form a cycle.

Steps:

1. Sort all edges in increasing order of weight.
2. Select the edge with the lowest weight.
3. If adding the edge does not form a cycle, include it in the MST.
4. Repeat until (V − 1) edges are included.

Time Complexity:

• Sorting edges → O(E log E)

Comparative Study of Prim and Kruskal

Advantages of MST

• Minimizes total cost.
• Optimizes network design.
• Avoids unnecessary edges.
• Easy to understand and implement.

Limitations of MST

• Applicable only to connected graphs.
• Works only on undirected graphs.
• Does not provide shortest path information.

Conclusion

The Minimum Spanning Tree is a crucial concept in graph theory.
It ensures all vertices are connected with minimum total cost.

Greedy algorithms like Prim’s and Kruskal’s efficiently find MSTs, making them essential tools in network design and optimization.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1