Minimum Spanning Tree: Definition, Example, and Uses

A minimum spanning tree (MST) is a subset of edges in a connected, weighted graph that connects all vertices with the smallest possible total edge weight and no cycles. It ensures every node is reachable with minimum cost.

How It Works

Imagine you want to connect several cities with roads so that every city is reachable from any other city. You want to use the least amount of road possible to save money. A minimum spanning tree helps find this cheapest way to connect all cities without any loops.

It works by picking edges (roads) one by one, always choosing the shortest available edge that doesn't create a cycle. This way, it gradually builds a network connecting all points with minimum total length.

Example

This example uses Kruskal's algorithm to find the minimum spanning tree of a graph represented by edges with weights.

python

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

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

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            elif self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False


def kruskal(n, edges):
    edges.sort(key=lambda x: x[2])  # Sort by weight
    ds = DisjointSet(n)
    mst = []
    total_weight = 0
    for u, v, w in edges:
        if ds.union(u, v):
            mst.append((u, v, w))
            total_weight += w
    return mst, total_weight

# Graph with 4 nodes and weighted edges
nodes = 4
edges = [
    (0, 1, 1),
    (0, 2, 4),
    (1, 2, 2),
    (1, 3, 6),
    (2, 3, 3)
]

mst, weight = kruskal(nodes, edges)
print("Edges in MST:", mst)
print("Total weight:", weight)

Output

Edges in MST: [(0, 1, 1), (1, 2, 2), (2, 3, 3)]
Total weight: 6

When to Use

Use a minimum spanning tree when you need to connect all points in a network with the least total cost. This is common in designing efficient networks like computer networks, road systems, or electrical grids.

For example, a company building fiber optic cables between offices wants to minimize cable length to reduce cost. MST algorithms help find the best layout.

Key Points

• An MST connects all nodes with minimum total edge weight.
• It contains no cycles, ensuring a tree structure.
• Common algorithms to find MST are Kruskal's and Prim's.
• Useful in network design and cost optimization problems.

Key Takeaways

A minimum spanning tree connects all nodes with the least total edge weight and no cycles.

Kruskal's and Prim's algorithms are popular methods to find MSTs efficiently.

MSTs are useful for designing cost-effective networks like roads, cables, or pipelines.

The MST ensures every point is reachable with minimum connection cost.

It helps solve real-world problems where minimizing total connection cost is critical.