Prim's Algorithm is typically used to find the minimum spanning tree (MST) of a graph, which
is a subset of the edges that connect all the vertices in the graph while minimizing the total edge
weight. While Prim’s algorithm is not directly a network flow algorithm, it is often used in
optimization problems where flow or connectivity in a graph needs to be minimized, such as in
network design.
In a network flow context, Prim’s algorithm can be used to find the minimum spanning tree
(MST) of a flow network, which helps minimize the overall cost or weight required to connect
all nodes.
A node can be visited once only so no cycles should be developed.
All nodes should be visited.
Here’s a step-by-step numerical example of Prim’s Algorithm for finding a Minimum Spanning
Tree (MST) of a graph.
Example 1
Let us consider the following graph (undirected and weighted):
Edge Weight
A-B 1
A-C 5
B-C 4
B-D 3
C-D 2
C-E 6
D-E 7
Step-by-Step Execution
Initial Setup:
1. Start from vertex A (arbitrary choice).
2. MST starts empty.
3. Keep track of visited nodes: initially only A is visited.
4. Add the edges connected to A into a priority queue (min-heap), sorted by weight.
1
Step 1: Start with A
Edges from A:
o A-B (weight 1)
o A-C (weight 5)
Select the smallest edge: A-B (weight 1).
Add B to the MST and mark it as visited.
Step 2: Consider B
Visited nodes: {A, B}.
Edges from B:
o B-C (weight 4)
o B-D (weight 3)
Add these edges to the priority queue. Now the queue contains:
o A-C (weight 5)
o B-C (weight 4)
o B-D (weight 3)
Select the smallest edge: B-D (weight 3).
Add D to the MST and mark it as visited.
Step 3: Consider D
Visited nodes: {A, B, D}.
Edges from D:
o D-C (weight 2)
o D-E (weight 7)
Add these edges to the priority queue. Now the queue contains:
o A-C (weight 5)
2
o B-C (weight 4)
o D-C (weight 2)
o D-E (weight 7)
Select the smallest edge: D-C (weight 2).
Add C to the MST and mark it as visited.
Step 4: Consider C
Visited nodes: {A, B, C, D}.
Edges from C:
o C-E (weight 6)
Add this edge to the priority queue. Now the queue contains:
o A-C (weight 5)
o B-C (weight 4)
o C-E (weight 6)
o D-E (weight 7)
Select the smallest edge: A-C (weight 5), but C is already visited, so skip it.
Next, consider C-E (weight 6).
Add E to the MST and mark it as visited.
Final MST
Edges in the MST:
A-B (weight 1)
B-D (weight 3)
D-C (weight 2)
C-E (weight 6)
Total Weight of MST: 1+3+2+6 = 12.
Example 2
3
Let's consider a weighted, undirected graph representing a network with 5 nodes (A, B, C, D, E).
The graph has the following edges with associated weights:
Edges:(A,B,4), (A,C,2), (B,C,5), (B,D,10), (C,D,3), (C,E,8), (D,E,7)
We will apply Prim’s Algorithm to find the Minimum Spanning Tree (MST) for this network.
Step-by-Step Process
1. Initialization:
o Start from an arbitrary node (let’s say node A).
o Initialize a priority queue to store the edge weights and the current minimum
spanning tree (MST).
o Mark all nodes as unvisited.
2. Iterate:
o Add the node with the smallest edge weight to the MST, and then explore its
neighbors. Update the priority queue accordingly.
o Repeat until all nodes are included in the MST.
4
Prim's Algorithm Execution
Let's apply Prim’s algorithm to the graph step by step.
Step 1: Start at Node A
The edges from A are:
o A→B with weight 4
o A→C with weight 2
Add the edge A→C (minimum weight edge) to the MST.
Step 2: Add Node C
The edges from C are:
o C→B with weight 5
o C→D with weight 3
o C→E with weight 8
Add the edge C→D with weight 3 to the MST.
Step 3: Add Node D
The edges from D are:
o D→B with weight 10
o D→E with weight 7
Add the edge D→E with weight 7 to the MST.
Step 4: Add Node B
o A→B with weight 4
Step 4: Add Node E
o D→E with weight 7
Minimum Spanning Tree (MST)
The edges included in the MST are:
MST Edges:(A,C,2),(C,D,3),(A,B,4),(D,E,7)
The total weight of the MST is 2+3+4+7 = 16.
5
Python Code for Prim’s Algorithm
Here’s the Python code to implement Prim’s algorithm for this problem:
import heapq
def prims_algorithm(graph, start):
"""
Perform Prim's algorithm to find the Minimum Spanning Tree (MST).
:param graph: Dictionary representing the adjacency list of the graph.
Format: {node: [(neighbor, weight), ...], ...}
:param start: Starting vertex for the algorithm.
:return: List of edges in the MST and the total weight of the MST.
"""
mst = [] # List to store edges of the MST
visited = set() # Set of visited nodes
min_heap = [] # Priority queue to select the minimum weight edge
# Add all edges of the starting vertex to the priority queue
for neighbor, weight in graph[start]:
heapq.heappush(min_heap, (weight, start, neighbor))
visited.add(start)
total_weight = 0 # Total weight of the MST
while min_heap:
weight, u, v = heapq.heappop(min_heap) # Get the edge with the smallest weight
if v not in visited: # If the destination node is not visited
visited.add(v) # Mark it as visited
mst.append((u, v, weight)) # Add the edge to the MST
total_weight += weight # Add the weight to the total
# Add all edges of the new vertex to the priority queue
for neighbor, edge_weight in graph[v]:
if neighbor not in visited:
heapq.heappush(min_heap, (edge_weight, v, neighbor))
return mst, total_weight
# Graph representation as an adjacency list
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('C', 5), ('D', 10)],
'C': [('A', 2), ('B', 5), ('D', 3), ('E', 8)],
'D': [('B', 10), ('C', 3), ('E', 7)],
'E': [('C', 8), ('D', 7)]
}
# Run Prim's algorithm starting from vertex 'A'
mst, total_weight = prims_algorithm(graph, 'A')
# Print the results
print("Minimum Spanning Tree (MST) edges:", mst)
6
print("Total weight of the MST:", total_weight)
Explanation of the Code:
1. Graph Representation: The graph is represented as an adjacency list where each node
has a list of tuples containing its neighbors and the associated edge weights.
2. Priority Queue (Min-Heap): We use a priority queue (min-heap) to efficiently fetch the
next minimum weight edge.
3. Visited Set: A set is used to keep track of the nodes that are already part of the MST.
4. MST Construction: The algorithm starts from the given starting node, and iteratively
selects the minimum weight edge that connects a new node to the MST. This process
continues until all nodes are included in the MST.
Output of Prim's Algorithm:
Minimum Spanning Tree (MST) edges: [(′A′,′C′,2),(′C′,′D′,3),(′A′,′B′,4),(′D′,′E′,7)]
Total weight of the MST: 16
Conclusion
The Minimum Spanning Tree (MST) includes the edges (A,C,2), (C,D,3),(A,B,4), and
(D,E,7).
The total weight of the MST is 16, representing the minimum total cost to connect all
nodes in the network.
This implementation and example show how Prim’s Algorithm can be applied to network flow
problems, specifically focusing on finding the minimum spanning tree.
