Example data

In the previous article, we explored Dijkstra’s algorithm and the A* algorithm—two widely used pathfinding algorithms that solve the shortest-path problem. In graph theory, however, another fundamental topic is the Minimum Spanning Tree (MST). This article delves into the concept of MSTs, their core algorithms, and practical applications.

Definition of Minimum Spanning Tree

In an undirected graph, a minimum spanning tree is a subgraph that includes all vertices, forms a tree (i.e., is acyclic), and has the minimum possible total edge weight among all such spanning trees.

Key Properties:

1. Contains All Vertices: An MST must include every vertex in the original graph.
2. Minimizes Total Edge Weight: The sum of the weights of its edges is the smallest among all possible spanning trees.
3. Uniqueness: If all edge weights are distinct, the MST is unique; if duplicate weights exist, multiple MSTs may be possible.

Common Algorithms

Kruskal’s Algorithm

Kruskal’s algorithm is an edge-based greedy algorithm. Its core idea is to sort all edges by weight in ascending order and iteratively select the smallest-weight edge that does not create a cycle when added to the growing spanning tree.

Algorithm Steps:

1. Sort all edges of the graph in non-decreasing order of weight.
2. Initialize an empty spanning tree.
3. Iterate over the sorted edges: for each edge, check whether adding it would form a cycle:
   • If no cycle is formed, include the edge in the spanning tree.
   • If a cycle would result, discard the edge.
4. Repeat step 3 until the spanning tree contains $V-1$ edges ($V$ = number of vertices).

Sample Code:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
    
    def find(self, u):
        if self.parent[u] != u:
            self.parent[u] = self.find(self.parent[u])  # Path compression
        return self.parent[u]
    
    def union(self, u, v):
        pu = self.find(u)
        pv = self.find(v)
        if pu != pv:
            self.parent[pu] = pv

def kruskal(vertices, edges):
    uf = UnionFind(len(vertices))
    mst = []
    edges.sort(key=lambda x: x[2])  # Sort by weight
    
    for u, v, weight in edges:
        if uf.find(u) != uf.find(v):
            uf.union(u, v)
            mst.append((u, v, weight))
    
    return mst

# Example data
vertices = [0, 1, 2, 3]
edges = [(0, 1, 1), (1, 2, 2), (2, 3, 1), (0, 3, 3), (1, 3, 2)]
mst = kruskal(vertices, edges)
print("Edges in the MST:", mst)

Time Complexity

Kruskal’s algorithm runs in $O(E \log E + E \log V)$ time, where $E$ is the number of edges and $V$ is the number of vertices.

Prim’s Algorithm

Prim’s algorithm is also a greedy algorithm—but it operates vertex-centrically. It starts from an arbitrary vertex and repeatedly adds the lightest edge connecting the current tree to an unvisited vertex.

Algorithm Steps:

1. Pick any starting vertex and mark it as visited.
2. Among all edges connecting visited vertices to unvisited ones, select the one with minimum weight; add its endpoint to the visited set.
3. Repeat step 2 until exactly $V - 1$ edges have been selected.

Sample Code:

import heapq

def prim(vertices, edges):
    graph = {v: [] for v in vertices}
    for u, v, weight in edges:
        graph[u].append((weight, v))
        graph[v].append((weight, u))
    
    mst = []
    visited = {vertices[0]}  # Start from the first vertex
    edges_heap = graph[vertices[0]]
    heapq.heapify(edges_heap)
    
    while edges_heap:
        weight, u = heapq.heappop(edges_heap)
        if u not in visited:
            visited.add(u)
            mst.append((vertices[0], u, weight))  # Record the edge
            for w, v in graph[u]:
                if v not in visited:
                    heapq.heappush(edges_heap, (w, v))
    
    return mst

# Example data
vertices = [0, 1, 2, 3]
edges = [(0, 1, 1), (1, 2, 2), (2, 3, 1), (0, 3, 3), (1, 3, 2)]
mst = prim(vertices, edges)
print("Edges in the MST:", mst)

Time Complexity

Prim’s algorithm runs in $O(E \log V)$ time, making it especially efficient for dense graphs.

Real-World Applications

Minimum spanning trees play a vital role in numerous practical domains, including:

1. Network Design: Constructing low-cost infrastructure networks—e.g., computer networks, power grids, or water distribution systems.
2. Clustering Analysis: In data science, MSTs help identify natural groupings by linking similar data points with minimal total distance.
3. Image Processing: Certain image segmentation techniques leverage MSTs to model relationships among pixels.

Summary

This article provided an in-depth look at the minimum spanning tree concept and two classic algorithms for computing it: Kruskal’s and Prim’s. In the next article, we will shift our focus to foundational network flow algorithms, exploring how to optimize flow and allocate resources across networks. Understanding MSTs lays essential groundwork for grasping more advanced network optimization techniques.