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