C Program to implement prims algorithm using greedy method
C Program to implement prims algorithm using greedy method
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 | #include<stdio.h> #include<conio.h> int n, cost[10][10]; void prim() { int i, j, startVertex, endVertex; int k, nr[10], temp, minimumCost = 0, tree[10][3]; /* For first smallest edge */ temp = cost[0][0]; for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { if (temp > cost[i][j]) { temp = cost[i][j]; startVertex = i; 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 (i = 0; i < n; i++) { if (cost[i][startVertex] < cost[i][endVertex]) nr[i] = startVertex; else nr[i] = 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 (i = 1; i < n - 1; i++) { 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[i][0] = k; tree[i][1] = nr[k]; tree[i][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 (i = 0; i < n - 1; i++) { for (j = 0; j < 3; j++) printf("%d", tree[i][j]); printf("\n"); } printf("\nMin cost : %d", minimumCost); } void main() { int i, j; clrscr(); printf("\nEnter the no. of vertices :"); scanf("%d", &n); printf("\nEnter the costs of edges in matrix form :"); for (i = 0; i < n; i++) for (j = 0; j < n; j++) { scanf("%d", &cost[i][j]); } printf("\nThe matrix is : "); for (i = 0; i < n; i++) { for (j = 0; j < n; j++) { printf("%d\t", cost[i][j]); } printf("\n"); } prim(); getch(); } |
Output :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | Enter the no. of vertices:- 3 Enter the costs of edges in matrix form:- 99 2 3 2 99 5 3 5 99 The matrix is:- 99 2 3 2 99 5 3 5 99 The min spanning tree is:- 0 1 2 2 0 3 Min cost:- 5 |