C Programming Code Examples C > Beginners Lab Assignments Code Examples C Program to implement prims algorithm using greedy method C Program to implement prims algorithm using greedy method #include<stdio.h> #include<conio.h> int n, cost[10][10]; void prim() { int x, j, startVertex, endVertex; int k, nr[10], temp, minimumCost = 0, tree[10][3]; /* For first smallest edge */ temp = cost[0][0]; for (x = 0; x < n; x++) { for (j = 0; j < n; j++) { if (temp > cost[x][j]) { temp = cost[x][j]; startVertex = x; endVertex = j; } } } /* Now we have fist smallest edge in graph */ tree[0][0] = startVertex; tree[0][1] = endVertex; tree[0][2] = temp; minimumCost = temp; /* Now we have to find min dis of each vertex from either startVertex or endVertex by initialising nr[] array */ for (x = 0; x < n; x++) { if (cost[x][startVertex] < cost[x][endVertex]) nr[x] = startVertex; else nr[x] = endVertex; } /* To indicate visited vertex initialise nr[] for them to 100 */ nr[startVertex] = 100; nr[endVertex] = 100; /* Now find out remaining n-2 edges */ temp = 99; for (x = 1; x < n - 1; x++) { for (j = 0; j < n; j++) { if (nr[j] != 100 && cost[j][nr[j]] < temp) { temp = cost[j][nr[j]]; k = j; } } /* Now i have got next vertex */ tree[x][0] = k; tree[x][1] = nr[k]; tree[x][2] = cost[k][nr[k]]; minimumCost = minimumCost + cost[k][nr[k]]; nr[k] = 100; /* Now find if k is nearest to any vertex than its previous near value */ for (j = 0; j < n; j++) { if (nr[j] != 100 && cost[j][nr[j]] > cost[j][k]) nr[j] = k; } temp = 99; } /* Now i have the answer, just going to print it */ printf("\nThe min spanning tree is:- "); for (x = 0; x < n - 1; x++) { for (j = 0; j < 3; j++) printf("%d", tree[x][j]); printf("\n"); } printf("\nMin cost : %d", minimumCost); } void main() { int x, j; clrscr(); printf("\nEnter the no. of vertices :"); scanf("%d", &n); printf("\nEnter the costs of edges in matrix form :"); for (x = 0; x < n; x++) for (j = 0; j < n; j++) { scanf("%d", &cost[x][j]); } printf("\nThe matrix is : "); for (x = 0; x < n; x++) { for (j = 0; j < n; j++) { printf("%d\t", cost[x][j]); } printf("\n"); } prim(); getch(); }