- Prepare
- All Platforms
- Programming
- Aptitude
- Syllabus
- Interview Preparation
- Interview Exp.
- Off Campus
- Prime Video
- Prime Mock

- Prime Video
- OffCampus
- Internship
- Placement Stats
- Prime Video
- Prime Mock

^{0}Notifications Mark All Read

No New notification

- Login
- Get Prime

# Minimum Spanning Tree

## Introduction to MST

Minimum Spanning Tree is a connected, undirected graph is a subset that encompasses all the graph’s vertices while adhering to the characteristics of a tree. These algorithms help optimize network design, minimize costs, and enhance the efficiency of communication and transportation systems.

In the context of finding a minimum spanning tree (MST), the goal is to find a spanning tree with the minimum possible total edge weight.

**What is Spanning Tree?
**

A spanning tree in a connected, undirected graph is a subset that encompasses all the graph’s vertices while adhering to the characteristics of a tree.

- To put it differently, it is a tree structure that covers every vertex of the original graph without forming any cycles.

Here are some key characteristics of a spanning tree:

**
Minimum Spanning Tree**

A Minimum Spanning Tree is a type of tree, indicating it is a connected, acyclic graph. It guarantees the existence of a single path between any two vertices, with the absence of cycles or loops within its structure.

**For Example :**

Imagine a network of cities connected by roads, where each road has a certain distance associated with it. A Minimum Spanning Tree for this network would be the subset of roads that connects all cities with the shortest total distance possible.

**Properties of Minimum Spanning Tree**

Following are the properties of Minimum Spanning Trees(MST) :

- Removing any edge from the spanning tree results in its disconnection.
- The addition of an edge to the spanning tree introduces a loop.
- In a graph where each edge possesses a unique weight, there exists only one distinct minimum spanning tree. Conversely, if edge weights are not distinct, there may be multiple minimum spanning trees.
- A complete undirected graph can have a total of
**n^(n-2)**spanning trees, where**‘n’**represents the number of vertices. - Every connected and undirected graph contains at least one spanning tree.
- A disconnected graph does not possess any spanning tree.
- In a complete graph, the maximum number of edges that can be removed to construct a spanning tree is ‘
**e – n + 1′,**where**‘e’**is the number of edges and**‘n’**is the number of vertices.

**Key Characteristics of MST**

**Algorithms for Finding MST**

Several algorithms can be employed to find the Minimum Spanning Tree of a graph, each with its own set of advantages and use cases. Some popular algorithms include:

**Kruskal’s Algorithm:**This algorithm grows the Minimum Spanning Tree one edge at a time by selecting the smallest available edge that doesn’t create a cycle.**Prim’s Algorithm:**Starting from an arbitrary vertex, this algorithm adds the shortest edge that connects a vertex outside the tree to the tree at each step.**Boruvka’s Algorithm:**This algorithm works by adding the smallest edge for each component of the graph in each iteration.

**1. Finding MST using Kruskal’s Algorithm**

This implementation assumes that the graph is represented as an adjacency list, where each node is a tuple of the form (weight, u, v) indicating an edge between vertices u and v with weight weight.

class DisjointSet: def __init__(self, vertices): self.parent = {vertex: vertex for vertex in vertices} self.rank = {vertex: 0 for vertex in vertices} def find(self, vertex): if self.parent[vertex] != vertex: self.parent[vertex] = self.find(self.parent[vertex]) return self.parent[vertex] def union(self, root1, root2): if self.rank[root1] > self.rank[root2]: self.parent[root2] = root1 elif self.rank[root1] < self.rank[root2]: self.parent[root1] = root2 else: self.parent[root2] = root1 self.rank[root1] += 1 def kruskal(graph): # Sort edges in ascending order of weight edges = sorted(graph, key=lambda x: x[0]) vertices = set() for edge in edges: vertices.add(edge[1]) vertices.add(edge[2]) disjoint_set = DisjointSet(vertices) minimum_spanning_tree = [] for edge in edges: weight, u, v = edge root1 = disjoint_set.find(u) root2 = disjoint_set.find(v) if root1 != root2: minimum_spanning_tree.append(edge) disjoint_set.union(root1, root2) return minimum_spanning_tree # Example usage: graph = [ (1, 'A', 'B'), (4, 'A', 'D'), (3, 'B', 'D'), (2, 'B', 'E'), (5, 'D', 'E'), (1, 'C', 'E') ] result = kruskal(graph) print("Minimum Spanning Tree:", result)

**Output **

Minimum Spanning Tree: [(1, 'A', 'B'), (1, 'C', 'E'), (2, 'B', 'E'), (3, 'B', 'D')]

**Application of Finding MST**

An overview of different sets of applications for finding MST :

**To Wrap it up: **

Understanding and efficiently finding the Minimum Spanning Tree of a graph is essential in various fields. Whether optimizing network connections, designing transportation systems, or minimizing wire lengths in circuits, the concept of Minimum Spanning Tree plays a pivotal role in creating efficient and cost-effective solutions.

### Prime Course Trailer

### Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

**Get over 200+ course One Subscription**

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Login/Signup to comment