Prim Algorithm - Finding Minimum Spanning Tree
Graph
In this tutorial we will learn to find Minimum Spanning Tree (MST) using Prim's algorithm.
Minimum Spanning Tree
A spanning tree of a graph is a tree that has all the vertices of the graph connected by some edges. A graph can have one or more number of spanning trees.
If the graph has N vertices then the spanning tree will have N-1 edges. A minimum spanning tree (MST) is a spanning tree that has the minimum weight than all other spanning trees of the graph.
Graph
Consider the following graph.
We will find MST for the above graph shown in the image.
Steps
Step 1: Remove all loops
Any edge that starts and ends at the same vertex is a loop.
Loops are marked in the image given below.
Step 2: Remove all parallel edges between two vertex except the one with least weight
In this graph, vertex A and C are connected by two parallel edges having weight 10 and 12 respectively. So, we will remove 12 and keep 10.
We are now ready to find the minimum spanning tree.
Step 3: Create table
As our graph has 4 vertices, so our table will have 4 rows and 4 columns.
Now, put 0 in cells having same row and column name.
Find the edges that directly connects two vertices and fill the table with the weight of the edge. If no direct edge exists then fill the cell with infinity.
Finding MST
Start from vertex A, find the smallest value in the A-row.
Note! We will not consider 0 as it will correspond to the same vertex.
5 is the smallest unmarked value in the A-row. So, we will mark the edge connecting vertex A and B and tick 5 in AB and BA cell.
As we connected vertex A and B in the previous step, so we will now find the smallest value in the A-row and B-row.
4 is the smallest unmarked value in the A-row and B-row. So, we will mark the edge connecting vertex B and C and tick 4 in BC and CB cell.
As vertex A-B and B-C were connected in the previous steps, so we will now find the smallest value in A-row, B-row and C-row.
5 is the smallest unmarked value in the A-row, B-row and C-row. So, we will mark the edge connecting vertex C and D and tick 5 in CD and DC cell.
Result
Following is the required Minimum Spanning Tree for the given graph.
Code
Note! In the given code we are representing Vertices using decimal numbers.
So,
vertex A is denoted by digit 0.
vertex B is denoted by digit 1.
vertex C is denoted by digit 2.
vertex D is denoted by digit 3.
/**
* file: prim.c
* author: yusuf shakeel
* date: 2014-03-02
*
* description: find MST using prim's algorithm
*
* vertices are represented using numbers.
* vertex A becomes 0
* vertex B becomes 1
* and so on...
*/
#include <stdio.h>
#include <stdlib.h>
/**
* contant to represent infinity
* it is assumed that edges of the graph will have weight less than this value
*/
#define INF 9999
/**
* total number of vertices in the graph
*/
#define V 4
/**
* this function will display the MST
*/
void displayMST(int graph[V][V], int markedCell[V][V]) {
int r, c;
for (r = 0; r < V-1; r++) {
for (c = r+1; c < V; c++) {
if(markedCell[r][c]) {
printf("Edge: %d -- %d\tWeight: %d\n", r, c, graph[r][c]);
}
}
}
}
/**
* prim&aposs algorithm function
*/
void prim(int graph[V][V]) {
//variables
int i, r, c,
solved = 0,
count = 0,
min,
expectedR,
expectedC;
/**
* this array holds the marked cells in the graph
*/
int markedCell[V][V] = {{0}};
/**
* this array holds the marked vertices
* 0 = unmarked
* 1 = marked
*/
int markedVertex[V] = {0};
markedVertex[0] = 1;
/**
* find MST
*/
while(!solved) {
min = INF;
count = 0;
expectedR = -1;
expectedC = -1;
/**
* find minimum weight from marked vertex
*
* note!
* graph[][] is a square matrix
* diagonal elements of the graph[][] are zeros
* and elements on either sides are same
* example: element graph[1][0] is same as graph[0][1]
* so, we will check only one side of the diagonal
*/
for (r = 0; r < V; r++) {
if (markedVertex[r] == 1) {
for (c = r; c < V; c++) {
if (graph[r][c] != 0 && graph[r][c] < min && !markedCell[r][c]) {
min = graph[r][c];
expectedR = r;
expectedC = c;
}
}
}
}
/**
* mark the newly found vertex for MST
*/
if (expectedR != -1 && expectedC != -1) {
markedCell[expectedR][expectedC] = 1;
markedCell[expectedC][expectedR] = 1;
markedVertex[expectedR] = 1;
markedVertex[expectedC] = 1;
}
/**
* check if the graph is solved
*/
for (i = 0; i < V; i++) {
if (markedVertex[i]) {
count++;
}
}
if (count == V) {
solved = 1;
}
}
displayMST(graph, markedCell);
}
/**
* this is the main function
*/
int main(void) {
/**
* 2d array which holds the weight of the edges
*
* note!
* graph[][] is a square matrix
* diagonal elements of the graph[][] are zeros
* and elements on either sides are same
* example: element graph[1][0] is same as graph[0][1]
*/
int graph[V][V] = {
{0, 5, 10, INF},
{5, 0, 4, 11},
{10, 4, 0, 5},
{INF, 11, 5, 0}
};
/**
* find MST using prim
*/
prim(graph);
return 0;
}
Output
Edge: 0 -- 1 Weight: 5
Edge: 1 -- 2 Weight: 4
Edge: 2 -- 3 Weight: 5
ADVERTISEMENT