Prim's Algorithm
The core of Prim's algorithm is its ability to find the Minimum Spanning Tree
(MST) of a weighted graph, ensuring the smallest possible total edge weight.
This greedy algorithm is widely used in network design, including computer
networks and roadway design, as it helps minimize the total cost
of connecting all vertices with the least number of edges.
Problem
Given a connected, weighted graph, the goal is to find a subset of edges that connects all
vertices with the minimum possible total edge weight, without forming any cycles.
The process of connecting the vertices using this subset of edges is known as finding the
Minimum Spanning Tree (MST).
Input
A connected, weighted graph represented by its vertices and edges.
Output
The edges that form the Minimum Spanning Tree (MST) along with their total weight.
Example:
- Edge 1 - (A, B) with weight 2
- Edge 2 - (B, C) with weight 3
- Edge 3 - (A, D) with weight 1
Types of Minimum Spanning Trees
1. Unique MST
In this case, there is only one unique Minimum Spanning Tree for the given graph.
2. Multiple MSTs
In this case, there can be more than one Minimum Spanning Tree due to edges with equal weights.
Prim's Algorithm and Min Heap
The Prim's algorithm builds the Minimum Spanning Tree (MST) in a step-by-step
manner, adding the smallest possible edge that connects a new vertex to the growing tree.
The algorithm follows these two main steps:
- Start from any vertex: Initialize the MST by choosing any vertex as the starting point.
- Add the smallest edge: At each step, add the smallest edge that connects a new vertex to the MST, ensuring no cycles are formed.
To optimize the process of selecting the smallest edge at each step, a Min Heap
data structure is often used.
The Min Heap acts as a priority queue, where the edge with the smallest weight is always at the
top.
This allows Prim's algorithm to efficiently choose the minimum weight edge that expands the MST.
Prim's Algorithm
Prim(N, Graph)
Input: An integer N representing the number of vertices, and a
Graph represented by an adjacency matrix or edge list.
Output: The Minimum Spanning Tree (MST) of the graph and its total weight.
Step 1: Start.
Step 2: Initialize an empty set MST to store the edges of the
Minimum Spanning Tree.
Step 3: Initialize a Min Heap to prioritize the edges with the
smallest weights.
Step 4: Select any vertex as the starting vertex and add its edges to the
Min Heap.
Step 5: While the number of edges in MST is less than
N - 1:
Step 6: Extract the edge with the minimum weight from the
Min Heap.
Step 7: If the edge connects a vertex not already in the
MST, add the edge to MST.
Step 8: Add the new vertex's edges to the
Min Heap.
Step 9: Continue this process until N - 1
edges are added to the MST.
Step 10: Once the MST is complete, calculate the total weight by summing the
weights of all edges in MST.
Step 11: Output the edges in the MST and their total weight.
Step 12: Stop.
Prim's Algorithm code
#include <stdio.h>
#include <limits.h>
#define V 5 // Number of vertices in graph
int minKey(int key[], int mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == 0 && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
printf("Edge \tWeight\n");
for (int i = 1; i < V; i++)
printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
void primMST(int graph[V][V]) {
int parent[V]; // Array to store constructed MST
int key[V]; // Key values to pick minimum weight edge
int mstSet[V]; // To represent set of vertices not yet included in MST
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = 0;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = 1;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
primMST(graph);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
#define V 5
int minKey(int key[], bool mstSet[]) {
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
void printMST(int parent[], int graph[V][V]) {
cout << "Edge \tWeight\n";
for (int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t" << graph[i][parent[i]] << " \n";
}
void primMST(int graph[V][V]) {
int parent[V];
int key[V];
bool mstSet[V];
for (int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false;
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
printMST(parent, graph);
}
int main() {
int graph[V][V] = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
primMST(graph);
return 0;
}
import java.util.*;
public class Prim {
private static final int V = 5;
int minKey(int key[], boolean mstSet[]) {
int min = Integer.MAX_VALUE, min_index = -1;
for (int v = 0; v < V; v++)
if (!mstSet[v] && key[v] < min) {
min = key[v];
min_index = v;
}
return min_index;
}
void printMST(int parent[], int graph[][]) {
System.out.println("Edge \tWeight");
for (int i = 1; i < V; i++)
System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
}
void primMST(int graph[][]) {
int parent[] = new int[V];
int key[] = new int[V];
boolean mstSet[] = new boolean[V];
for (int i = 0; i < V; i++) {
key[i] = Integer.MAX_VALUE;
mstSet[i] = false;
}
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < V - 1; count++) {
int u = minKey(key, mstSet);
mstSet[u] = true;
for (int v = 0; v < V; v++)
if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
printMST(parent, graph);
}
public static void main(String[] args) {
Prim t = new Prim();
int graph[][] = new int[][]{{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
t.primMST(graph);
}
}
import sys
V = 5
def minKey(key, mstSet):
min = sys.maxsize
for v in range(V):
if key[v] < min and not mstSet[v]:
min = key[v]
min_index = v
return min_index
def printMST(parent, graph):
print("Edge \tWeight")
for i in range(1, V):
print(f"{parent[i]} - {i} \t{graph[i][parent[i]]}")
def primMST(graph):
key = [sys.maxsize] * V
parent = [None] * V
key[0] = 0
mstSet = [False] * V
parent[0] = -1
for _ in range(V):
u = minKey(key, mstSet)
mstSet[u] = True
for v in range(V):
if graph[u][v] and not mstSet[v] and key[v] > graph[u][v]:
key[v] = graph[u][v]
parent[v] = u
printMST(parent, graph)
graph = [[0, 2, 0, 6, 0],
[2, 0, 3, 8, 5],
[0, 3, 0, 0, 7],
[6, 8, 0, 0, 9],
[0, 5, 7, 9, 0]]
primMST(graph)
Time Complexity of Prim's Algorithm
Time Complexity Basic Operation: Edge Selection and Min Heap Operations
Analysis
The time complexity of Prim's Algorithm varies based on the data structure used for the graph representation and the priority queue (Min Heap). Let's analyze both scenarios:
1. Using an Adjacency Matrix: In this case, Prim's algorithm runs in
O(N^2), where N is the number of vertices. This is because for each
vertex, we need to find the smallest edge connecting it to the MST, which takes
O(N) time for each of the N vertices.
2. Using an Adjacency List and Min Heap: If we use an adjacency list along with
a Min Heap to extract the minimum weight edge efficiently, the time complexity becomes
O((N + E) log N), where N is the number of vertices and E
is the number of edges. The breakdown is as follows:
1. Inserting or updating an edge in the Min Heap takes O(log N) time.
2. We perform this operation for each edge adjacent to every vertex, leading to O(E log N) for all edges.
3. Extracting the minimum weight edge from the heap takes O(log N), and this is done N times.
Hence, the total time complexity in this case is O((N + E) log N), making the
adjacency list representation with a Min Heap more efficient for sparse graphs.