In [1]: import networkx as nx
import [Link] as plt
import time
In [2]: # Create a weighted graph
G = [Link]()
edges = [
('A', 'B', 4), ('A', 'H', 8), ('B', 'H', 11), ('B', 'C', 8), ('C'
('C', 'F', 4), ('C', 'I', 2), ('D', 'E', 9), ('D', 'F', 14), ('E'
('F', 'G', 2), ('G', 'H', 1), ('G', 'I', 6), ('H', 'I', 7)
]
G.add_weighted_edges_from(edges)
🧩 What is a Minimum Spanning Tree?
A spanning tree of a graph is a subset of the edges that connects all vertices without
any cycles.
A minimum spanning tree is a spanning tree with the least total weight.
🌲 Prim’s Algorithm for Minimum
Spanning Tree (MST)
🧠 Goal
Prim’s Algorithm finds a Minimum Spanning Tree (MST) for a connected, undirected,
and weighted graph.
It returns a subset of edges $T \subseteq E$ such that:
$T$ forms a tree (i.e., no cycles),
$T$ connects all vertices: $T$ spans $V$,
The total weight is minimized:
$$ \min_{T \subseteq E} \sum_{(u,v) \in T} w(u,v) $$
📐 Notation
Let $G = (V, E)$ be an undirected weighted graph with:
$V$: set of nodes/vertices
$E$: set of edges
$w(u,v)$: weight of edge between $u$ and $v$
$A$: set of vertices already added to the MST (i.e., visited)
$T$: set of edges in the MST
🔍 Prim’s Algorithm — Step-by-Step
1. Initialize:
Choose any start vertex $v_0 \in V$
Let $A = \{v_0\}$ (visited set)
Let $T = \emptyset$ (MST edge set)
2. Repeat until $|A| = |V|$:
Among all edges $(u, v)$ such that:
$u \in A$
$v \in V \setminus A$
Choose the edge with minimum weight:
$$ (u^*, v^*) = \arg\min_{u \in A, v \in V \setminus A} w(u, v) $$
Add $v^*$ to $A$:
$$ A \leftarrow A \cup \{v^*\} $$
Add edge $(u^*, v^*)$ to $T$:
$$ T \leftarrow T \cup \{(u^*, v^*)\} $$
3. Return the MST edge set $T$
✅ Conditions
Prim’s algorithm works when:
$G$ is connected
$G$ is undirected
All edge weights are non-negative
In [4]: def draw_prim_step(G, pos, mst_edges, visited, current=None, candidate_ed
[Link]()
# Node colors
node_colors = []
for node in [Link]():
if node == current:
node_colors.append('orange') # Current node
elif node in visited:
node_colors.append('lightgreen') # In MST
else:
node_colors.append('skyblue') # Not in MST
# Edge colors
edge_colors = []
for edge in [Link]():
if edge in mst_edges or (edge[1], edge[0]) in mst_edges:
edge_colors.append('green') # In MST
elif edge == candidate_edge or (edge[1], edge[0]) == candidate_ed
edge_colors.append('red') # Candidate edge
else:
edge_colors.append('gray') # Default
[Link](G, pos, with_labels=True, node_color=node_colors, edge_color=
edge_labels = nx.get_edge_attributes(G, 'weight')
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
if current:
[Link](f"Current node: {current} | Building MST...", fontsize=
else:
[Link]("Final MST", fontsize=10)
[Link](1)
def prim_visual_step_by_step(G):
pos = nx.spring_layout(G, seed=42)
visited = set()
mst_edges = []
source = 'A'
[Link](source)
[Link]()
fig = [Link](figsize=(8, 6))
while len(visited) < len([Link]()):
# Step: from visited nodes, find the smallest edge to an unvisite
candidate = None
min_weight = float('inf')
for u in visited:
for v in [Link](u):
if v in visited:
continue
weight = G[u][v]['weight']
if weight < min_weight:
min_weight = weight
candidate = (u, v)
if candidate:
u, v = candidate
print(f"\nAdding edge ({u}, {v}) with weight {min_weight} to M
[Link](v)
mst_edges.append((u, v))
draw_prim_step(G, pos, mst_edges, visited, current=v, candida
# Final visualization
draw_prim_step(G, pos, mst_edges, visited)
[Link]()
[Link]()
# Run Prim's Algorithm with visualization
prim_visual_step_by_step(G)
Adding edge (A, B) with weight 4 to MST
Adding edge (B, C) with weight 8 to MST
Adding edge (C, I) with weight 2 to MST
Adding edge (C, F) with weight 4 to MST
Adding edge (F, G) with weight 2 to MST
Adding edge (G, H) with weight 1 to MST
Adding edge (C, D) with weight 7 to MST
Adding edge (D, E) with weight 9 to MST
📐 Proposition: Correctness of Prim’s Algorithm
By Theorem (Cut Property):
For any edge cut in the graph, the minimum-weight edge crossing that cut
belongs to every Minimum Spanning Tree (MST).
✨ Argument
At each step, Prim’s algorithm maintains a set $S$ of vertices already included in
the tree.
It looks at all edges crossing the cut $(S, V \setminus S)$ and picks the minimum-
weight edge.
By the Cut Property, this edge must belong to every MST.
Therefore, Prim’s algorithm never makes a “wrong” choice.
🌳 Why the output is a spanning tree
1. Connectivity:
Each step adds exactly one edge that connects a new vertex to $S$.
Thus the tree grows by one vertex each time, ensuring connectivity.
2. No cycles:
Since exactly one new vertex is added at each step, no cycles can be formed.
The structure remains a tree at every stage.
3. Minimality:
Every edge chosen is guaranteed by the Cut Property to appear in some MST.
By repeatedly applying this property, the final tree must be an MST.
In [ ]:
