IMPLEMENTATION OF PRIM’S ALGORITHM
Aim:
To write a C program for the implementation of Prim’s algorithm.
Algorithm:
1. Input the number of vertices vertices.
2. Input the adjacency matrix graph[MAX_VERTICES][MAX_VERTICES].
3. Set all key[] values to INT_MAX and all mstSet[] values to 0 (false).
4. Set key[0] = 0 to start with the first vertex in the MST.
5. Set parent[0] = -1 because the first vertex is the root of the MST.
6. Call the function minKey() to select the vertex u that has the smallest key value
and is not included in mstSet[].
7. Mark the vertex u as included in the MST (mstSet[u] = 1).
8. For each vertex v, if graph[u][v] is non-zero, v is not yet included in the MST
(mstSet[v] == 0), and the weight graph[u][v] is less than key[v], update
key[v] and parent[v].
9. Print the edges of the MST by traversing the parent[] array.
10. Calculate and print the total cost of the MST.
Program:
#include <stdio.h>
#include <limits.h>
#define MAX_VERTICES 100
// Function to find the vertex with the minimum key value
int minKey(int key[], int mstSet[], int vertices) {
int min = INT_MAX, minIndex;
for (int v = 0; v < vertices; v++) {
if (mstSet[v] == 0 && key[v] < min) {
min = key[v];
minIndex = v;
}
}
return minIndex;
}
// Function to implement Prim's algorithm
void primMST(int graph[MAX_VERTICES][MAX_VERTICES], int vertices) {
int parent[MAX_VERTICES]; // Array to store constructed MST
int key[MAX_VERTICES]; // Key values used to pick minimum weight edge
int mstSet[MAX_VERTICES]; // To represent vertices included in MST
int totalcost;
// Initialize all keys as infinite and mstSet[] as false
for (int i = 0; i < vertices; i++) {
key[i] = INT_MAX;
mstSet[i] = 0;
}
// Always include the first vertex in the MST
key[0] = 0; // Make key 0 so that this vertex is picked as the first
parent[0] = -1; // First node is the root of the MST
// The MST will have V vertices
for (int count = 0; count < vertices - 1; count++) {
// Pick the minimum key vertex from the set of vertices not yet included in MST
int u = minKey(key, mstSet, vertices);
mstSet[u] = 1; // Add the picked vertex to the MST
// Update the key value and parent index of the adjacent vertices
for (int v = 0; v < vertices; v++) {
// Update key only if graph[u][v] is non-zero, mstSet[v] is false,
// and graph[u][v] is less than key[v]
if (graph[u][v] && mstSet[v] == 0 && graph[u][v] < key[v]) {
parent[v] = u;
key[v] = graph[u][v];
}
}
}
// Print the constructed MST
printf("Edge \tWeight\n");
for (int i = 1; i < vertices; i++) {
printf("%d - %d \t%d\n", parent[i], i, graph[i][parent[i]]);
totalcost += graph[i][parent[i]];
}
printf("Total cost of MST: %d\n", totalcost);
}
int main() {
int vertices;
// Input the number of vertices
printf("Input the number of vertices: ");
scanf("%d", &vertices);
if (vertices <= 0 || vertices > MAX_VERTICES) {
printf("Invalid number of vertices. Exiting...\n");
return 1;
}
int graph[MAX_VERTICES][MAX_VERTICES];
// Input the adjacency matrix representing the weighted graph
printf("Input the adjacency matrix for the graph (use 0 for no edge):\n");
for (int i = 0; i < vertices; i++) {
for (int j = 0; j < vertices; j++) {
scanf("%d", &graph[i][j]);
}
}
// Perform Prim's algorithm
primMST(graph, vertices);
return 0;
}
Output:
Input the number of vertices: 4
Input the adjacency matrix for the graph (use 0 for no edge):
0206
2038
0300
6800
Edge Weight
0–1 2
1-2 3
0-3 6
Total cost of MST: 11
Result:
Thus the C program for implementation of Prim’s algorithm was successfully executed and
verified.
