DSA Minimum Spanning Tree
A minimum spanning tree connects every vertex in a weighted graph using the smallest possible total edge weight, with no cycles.
What Is a Minimum Spanning Tree?
A spanning tree of a connected graph is a subset of its edges that connects every vertex without forming a cycle, using exactly V - 1 edges for V vertices. A minimum spanning tree (MST) is the spanning tree whose edges sum to the lowest possible total weight. MSTs are used to design cost-efficient networks, such as laying the least amount of cable needed to connect a set of buildings, or the cheapest set of roads that keeps every town reachable.
Kruskal's Algorithm
Kruskal's algorithm builds the MST by considering edges in ascending order of weight, adding an edge only if it connects two vertices that are not already connected, since connecting them again would create a cycle. To test that efficiently, it uses a disjoint-set (union-find) data structure that tracks which component each vertex currently belongs to.
Example 1: Kruskal's Algorithm with Union-Find
def find(parent, vertex):
while parent[vertex] != vertex:
parent[vertex] = parent[parent[vertex]] # path compression
vertex = parent[vertex]
return vertex
def union(parent, rank, v1, v2):
root1, root2 = find(parent, v1), find(parent, v2)
if root1 == root2:
return False # already connected: adding this edge would form a cycle
if rank[root1] < rank[root2]:
root1, root2 = root2, root1
parent[root2] = root1
if rank[root1] == rank[root2]:
rank[root1] += 1
return True
def kruskal(vertices, edges):
parent = {v: v for v in vertices}
rank = {v: 0 for v in vertices}
mst = []
for weight, v1, v2 in sorted(edges):
if union(parent, rank, v1, v2):
mst.append((v1, v2, weight))
return mst
vertices = ["A", "B", "C", "D"]
edges = [(1, "A", "B"), (4, "A", "C"), (3, "B", "C"), (2, "B", "D"), (5, "C", "D")]
print(kruskal(vertices, edges))
# [('A', 'B', 1), ('B', 'D', 2), ('B', 'C', 3)]
Prim's Algorithm
Prim's algorithm grows the MST one vertex at a time instead of one edge at a time. Starting from an arbitrary vertex, it repeatedly adds the lowest-weight edge that connects a vertex already in the tree to a vertex outside it, much like Dijkstra's algorithm but tracking the weight of a single connecting edge rather than a cumulative path distance.
Example 2: Prim's Algorithm with a Priority Queue
import heapq
def prim(graph, start):
visited = {start}
edges = [(weight, start, neighbor) for neighbor, weight in graph[start]]
heapq.heapify(edges)
mst = []
while edges and len(visited) < len(graph):
weight, frm, to = heapq.heappop(edges)
if to in visited:
continue
visited.add(to)
mst.append((frm, to, weight))
for neighbor, next_weight in graph[to]:
if neighbor not in visited:
heapq.heappush(edges, (next_weight, to, neighbor))
return mst
graph = {
"A": [("B", 1), ("C", 4)],
"B": [("A", 1), ("C", 3), ("D", 2)],
"C": [("A", 4), ("B", 3), ("D", 5)],
"D": [("B", 2), ("C", 5)],
}
print(prim(graph, "A"))
# [('A', 'B', 1), ('B', 'D', 2), ('B', 'C', 3)]
- Kruskal's works on edges directly and needs them sorted, or held in a min-heap, up front.
- Prim's works on vertices, growing one connected tree outward, similar to Dijkstra's algorithm.
- Kruskal's, with union-find, tends to be simpler to reason about for sparse graphs.
- Prim's, with a binary heap, tends to be faster on dense graphs since it never needs a global edge sort.
- Both algorithms are greedy, and both are guaranteed to produce a valid minimum spanning tree.
Example 3: Total Weight and Spanning Forests
def mst_total_weight(mst_edges):
return sum(weight for _, _, weight in mst_edges)
vertices = ["A", "B", "C", "D"]
edges = [(1, "A", "B"), (4, "A", "C"), (3, "B", "C"), (2, "B", "D"), (5, "C", "D")]
mst_edges = kruskal(vertices, edges)
print("Total MST weight:", mst_total_weight(mst_edges)) # 6
# A minimum spanning tree only exists if the graph is connected;
# otherwise you get a minimum spanning forest, one tree per component.
print("Edges used:", len(mst_edges), "for", len(vertices), "vertices") # 3 edges for 4 vertices
Exercise: DSA Minimum Spanning Tree
What does a minimum spanning tree connect in a graph?
