Minimum Spanning Tree: Prim & Kruskal Algorithms

A Minimum Spanning Tree (MST) of a weighted, connected, and undirected graph is a spanning tree with the minimum possible sum of edge weights, connecting all vertices without cycles.

Prim’s Algorithm

Prim’s algorithm grows the minimum spanning tree by starting from an arbitrary node and repeatedly adding the cheapest possible edge that connects a new vertex to the existing tree.

How Prim’s Algorithm Works

• Initialize the MST with a starting vertex.
• At each step, add the minimum weight edge connecting a vertex in MST to a vertex outside MST.
• Repeat until all vertices are included.

Python Code Example

import sys

def prim(graph):
    V = len(graph)
    selected = [False] * V
    selected[0] = True
    edges = []
    total_weight = 0

    for _ in range(V - 1):
        minimum = sys.maxsize
        x = 0
        y = 0
        for i in range(V):
            if selected[i]:
                for j in range(V):
                    if (not selected[j]) and graph[i][j]:
                        if minimum > graph[i][j]:
                            minimum = graph[i][j]
                            x = i
                            y = j
        edges.append((x, y, graph[x][y]))
        total_weight += graph[x][y]
        selected[y] = True

    print("Edges in MST by Prim's Algorithm:")
    for edge in edges:
        print(f"{edge[0]} - {edge[1]}: {edge[2]}")
    print("Total weight:", total_weight)

# Example usage:
graph = [
    [0, 2, 0, 6, 0],
    [2, 0, 3, 8, 5],
    [0, 3, 0, 0, 7],
    [6, 8, 0, 0, 9],
    [0, 5, 7, 9, 0]
]

prim(graph)

Kruskal’s Algorithm

Kruskal’s algorithm builds the MST by sorting all edges in increasing order by weight and adding edges one by one, avoiding cycles using the Disjoint Set Union (Union-Find) data structure.

How Kruskal’s Algorithm Works

• Sort all edges of the graph by their weights.
• Add edges to the MST from lowest to highest weight, skipping edges that form cycles.
• Use Union-Find to detect cycles.
• Stop when MST contains (V-1) edges.

Python Code Example

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])
        return self.parent[u]

    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_u] = root_v
            elif self.rank[root_u] > self.rank[root_v]:
                self.parent[root_v] = root_u
            else:
                self.parent[root_v] = root_u
                self.rank[root_u] += 1
            return True
        return False

def kruskal(edges, V):
    ds = DisjointSet(V)
    mst = []
    edges.sort(key=lambda x: x[2])  # Sort by weight

    for u, v, weight in edges:
        if ds.union(u, v):
            mst.append((u, v, weight))
            if len(mst) == V - 1:
                break

    print("Edges in MST by Kruskal's Algorithm:")
    total_weight = 0
    for u, v, weight in mst:
        print(f"{u} - {v}: {weight}")
        total_weight += weight
    print("Total weight:", total_weight)

# Example usage:
edges = [
    (0, 1, 2),
    (0, 3, 6),
    (1, 2, 3),
    (1, 4, 5),
    (2, 4, 7),
    (3, 4, 9)
]
V = 5

kruskal(edges, V)

Use Cases of Minimum Spanning Trees

• Design of efficient network layouts (LAN, road networks, utility grids).
• Clustering algorithms in machine learning.
• Approximation algorithms for the traveling salesman problem.