# 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.

### 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:

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.

### 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