DSA Minimum Spanning Tree (MST)

Welcome to TheCodingCollege.com! Today, we’ll explore the Minimum Spanning Tree (MST), a fundamental concept in graph theory and Data Structures and Algorithms (DSA). MSTs are essential for solving problems related to optimization and resource management in networks.

What is a Minimum Spanning Tree?

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

Key Properties of MST:

1. Contains V−1V – 1 edges, where VV is the number of vertices.
2. Ensures no cycles are formed.
3. Total weight of the MST is minimized.

Applications of MST

• Network Design: Creating cost-effective layouts for communication, electrical, and transportation networks.
• Approximation Algorithms: Solving problems like the Traveling Salesman Problem.
• Clustering: Dividing data points into groups based on proximity.

Approaches to Find MST

Two popular algorithms are used to compute the MST:

1. Kruskal’s Algorithm: Greedy algorithm that sorts edges by weight.
2. Prim’s Algorithm: Greedy algorithm that builds the MST starting from a single vertex.

Kruskal’s Algorithm

Steps:

1. Sort all edges by weight.
2. Use a disjoint-set data structure to track connected components.
3. Add edges to the MST in ascending weight order, ensuring no cycles are formed.

Implementation:

class DisjointSet:
    def __init__(self, vertices):
        self.parent = {v: v for v in vertices}
        self.rank = {v: 0 for v 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, u, v):
        root_u = self.find(u)
        root_v = self.find(v)
        if root_u != root_v:
            if self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            elif self.rank[root_u] < self.rank[root_v]:
                self.parent[root_u] = root_v
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1

def kruskal_mst(graph, vertices):
    disjoint_set = DisjointSet(vertices)
    mst = []
    graph.sort(key=lambda x: x[2])  # Sort edges by weight

    for u, v, weight in graph:
        if disjoint_set.find(u) != disjoint_set.find(v):
            disjoint_set.union(u, v)
            mst.append((u, v, weight))

    return mst

# Example Usage
graph = [
    (0, 1, 10), (0, 2, 6), (0, 3, 5),
    (1, 3, 15), (2, 3, 4)
]
vertices = [0, 1, 2, 3]
mst = kruskal_mst(graph, vertices)
print("Edges in MST:", mst)

Prim’s Algorithm

Steps:

1. Start from an arbitrary vertex and add it to the MST.
2. Add the smallest edge connecting a vertex in the MST to a vertex outside it.
3. Repeat until all vertices are included.

Implementation:

import heapq

def prim_mst(graph, vertices):
    visited = set()
    mst = []
    min_heap = [(0, 0)]  # (weight, vertex)
    heapq.heapify(min_heap)

    while min_heap and len(visited) < vertices:
        weight, u = heapq.heappop(min_heap)
        if u not in visited:
            visited.add(u)
            mst.append((u, weight))

            for v, w in graph[u]:
                if v not in visited:
                    heapq.heappush(min_heap, (w, v))

    return mst

# Example Usage
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
vertices = 4
mst = prim_mst(graph, vertices)
print("Edges in MST:", mst)

Comparison of Kruskal’s and Prim’s Algorithm

Dry Run Example

Graph Example

• Vertices: 0,1,2,30, 1, 2, 3
• Edges:
  • (0,1,10)(0, 1, 10)
  • (0,2,6)(0, 2, 6)
  • (0,3,5)(0, 3, 5)
  • (1,3,15)(1, 3, 15)
  • (2,3,4)(2, 3, 4)

Using Kruskal’s Algorithm:

1. Sort edges: (2,3,4)(2, 3, 4), (0,3,5)(0, 3, 5), (0,2,6)(0, 2, 6), (0,1,10)(0, 1, 10), (1,3,15)(1, 3, 15).
2. Add edges:
   • (2,3,4)(2, 3, 4), (0,3,5)(0, 3, 5), (0,1,10)(0, 1, 10).

MST Edges: (2,3,4)(2, 3, 4), (0,3,5)(0, 3, 5), (0,1,10)(0, 1, 10).

Conclusion

The Minimum Spanning Tree is an essential concept in DSA, with applications ranging from optimizing networks to solving real-world problems efficiently. By mastering MST algorithms, you can tackle many graph-related challenges with ease.