WikiGalaxy
Prim's Minimum Spanning Tree Algorithm
Introduction
Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph. This means it finds a subset of the edges that forms a tree including every vertex, where the total weight of all the edges in the tree is minimized.
Example 1: Basic Graph
Graph Description
Consider a simple graph with four vertices (A, B, C, D) and edges with weights: A-B (1), B-C (3), C-D (4), and A-D (2).
Steps to Solve
Start from vertex A. Choose the edge with the smallest weight, A-B (1). From B, choose the smallest edge not forming a cycle, B-C (3). Finally, add C-D (4) to complete the MST.
// Java implementation of Prim's algorithm for MST
import java.util.*;
class PrimExample {
static final int V = 4;
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 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);
}
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]]);
}
public static void main(String[] args) {
PrimExample t = new PrimExample();
int graph[][] = new int[][]{{0, 1, 0, 2}, {1, 0, 3, 0}, {0, 3, 0, 4}, {2, 0, 4, 0}};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 1 1 0 - 3 2 1 - 2 3
Example 2: Complex Graph
Graph Description
Consider a graph with five vertices (A, B, C, D, E) and edges with weights: A-B (2), A-C (3), B-C (1), B-D (4), C-D (5), D-E (6).
Steps to Solve
Begin at vertex A. Select edge A-B (2). From B, choose B-C (1). Add C-D (5). Finally, add D-E (6) to complete the MST.
// Java implementation of Prim's algorithm for MST
import java.util.*;
class PrimExampleComplex {
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 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);
}
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]]);
}
public static void main(String[] args) {
PrimExampleComplex t = new PrimExampleComplex();
int graph[][] = new int[][]{{0, 2, 3, 0, 0}, {2, 0, 1, 4, 0}, {3, 1, 0, 5, 0}, {0, 4, 5, 0, 6}, {0, 0, 0, 6, 0}};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 1 2 1 - 2 1 2 - 3 5 3 - 4 6
Example 3: Sparse Graph
Graph Description
This graph has six vertices (A, B, C, D, E, F) with sparse connections: A-B (4), B-C (2), C-D (3), D-E (5), E-F (1).
Steps to Solve
Start from A. Choose A-B (4). From B, select B-C (2). Continue with C-D (3), D-E (5), and finally E-F (1) to form the MST.
// Java implementation of Prim's algorithm for MST
import java.util.*;
class PrimExampleSparse {
static final int V = 6;
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 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);
}
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]]);
}
public static void main(String[] args) {
PrimExampleSparse t = new PrimExampleSparse();
int graph[][] = new int[][]{{0, 4, 0, 0, 0, 0}, {4, 0, 2, 0, 0, 0}, {0, 2, 0, 3, 0, 0}, {0, 0, 3, 0, 5, 0}, {0, 0, 0, 5, 0, 1}, {0, 0, 0, 0, 1, 0}};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 1 4 1 - 2 2 2 - 3 3 3 - 4 5 4 - 5 1
Example 4: Dense Graph
Graph Description
A dense graph with vertices (A, B, C, D, E) and multiple edges: A-B (2), A-C (3), A-D (1), B-C (4), B-D (2), C-D (5), C-E (6), D-E (7).
Steps to Solve
Start at A. Choose A-D (1). From D, select B-D (2). Then choose C-B (4) and finally C-E (6) to form the MST.
// Java implementation of Prim's algorithm for MST
import java.util.*;
class PrimExampleDense {
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 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);
}
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]]);
}
public static void main(String[] args) {
PrimExampleDense t = new PrimExampleDense();
int graph[][] = new int[][]{{0, 2, 3, 1, 0}, {2, 0, 4, 2, 0}, {3, 4, 0, 5, 6}, {1, 2, 5, 0, 7}, {0, 0, 6, 7, 0}};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 3 1 3 - 1 2 1 - 2 4 2 - 4 6
Example 5: Graph with Equal Weights
Graph Description
Consider a graph where all edges have the same weight: A-B (1), A-C (1), B-D (1), C-D (1), D-E (1).
Steps to Solve
Start from A. Choose any edge, for instance, A-B (1). Then B-D (1), followed by C-D (1), and finally D-E (1) to complete the MST.
// Java implementation of Prim's algorithm for MST
import java.util.*;
class PrimExampleEqualWeights {
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 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);
}
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]]);
}
public static void main(String[] args) {
PrimExampleEqualWeights t = new PrimExampleEqualWeights();
int graph[][] = new int[][]{{0, 1, 1, 0, 0}, {1, 0, 0, 1, 0}, {1, 0, 0, 1, 0}, {0, 1, 1, 0, 1}, {0, 0, 0, 1, 0}};
t.primMST(graph);
}
}
Console Output:
Edge Weight 0 - 1 1 1 - 3 1 2 - 3 1 3 - 4 1
