MST PRIMS.c

#include <stdio.h>
#include <limits.h>
 
#define V 5
 
int minKey(int key[], int mstSet[]) {
    int min = INT_MAX, min_index;
    int v;
    for (v = 0; v < V; v++)
        if (mstSet[v] == 0 && key[v] < min)
            min = key[v], min_index = v;
 
    return min_index;
}
 
int printMST(int parent[], int n, int graph[V][V]) {
    int i,sum=0;
    printf("Edge   Weight\n");
    for (i = 1; i < V; i++)
        printf("%d - %d    %d \n", parent[i], i, graph[i][parent[i]]);
    for(i=1;i<V;i++)
    {
    	sum+=graph[i][parent[i]];
	}
	printf("minimum cost of tree is %d",sum);
}
 
void primMST(int graph[V][V]) {
    int parent[V]; 
    int key[V], i, v, count; 
    int mstSet[V];
    for (i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = 0;
    key[0] = 0;
    parent[0] = -1; 

    for (count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet);
        mstSet[u] = 1;
 
        for (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, V, graph);
}
 
int main() {
    int graph[V][V] = { { 0, 5, 10, 0, 0 }, { 5, 0, 0, 2, 6 },
            { 10, 0, 0, 15, 0 }, { 0, 2, 15, 0, 8 }, { 0, 6, 0, 8, 0 }, };
 
    
    primMST(graph);
 
    return 0;
}