Prim's algorithm in c
On-campus and online computer science courses to Learn the basic concepts of Computer Science.This tutorial will cover c ,c++, java, data structure and algorithm,computer graphics,microprocessor,analysis of algorithms,Digital Logic Design and Analysis,computer architecture,computer networks,operating system.
code in C:# include<stdio.h> int G[50][50],select[50], i, j, k, n, min_dist,total=0,u, v; /* This function finds the minimal spanning tree by Prim's Algorithm */ void Prim() { printf("\n\n The Minimal Spanning Tree Is :\n"); select[0] = 1; for (k=1 ; k<n ; k++) { min_dist = 32767; for (i=0 ; i<n ; i++) for (j=0 ; j<n ; j++) if (G[i][j] && ((select[i] && !select[j]) || (!select[i] && select[j]))) if (G[i][j] < min_dist) { min_dist = G[i][j]; u = i; v = j; } printf("\n Edge (%d %d )and weight = %d",u,v,min_dist); select[u] = select[v] = 1; total =total+min_dist; } printf("\n\n\t Total Path Length Is = %d",total); } int main() { printf("\n Enter Number of Nodes in The Graph: "); scanf("%d",&n); //entering weighted graph for(i=0;i<n;i++) { printf("\n"); for(j=0;j<n;j++) { printf("a[%d][%d]: ",i,j); scanf("%d",&G[i][j]); } } Prim(); return 0; }output:-
Enter Number of Nodes in The Graph: 6 a[0][0]: 0 a[0][1]: 3 a[0][2]: 1 a[0][3]: 6 a[0][4]: 0 a[0][5]: 0 a[1][0]: 3 a[1][1]: 0 a[1][2]: 5 a[1][3]: 0 a[1][4]: 3 a[1][5]: 0 a[2][0]: 1 a[2][1]: 5 a[2][2]: 0 a[2][3]: 5 a[2][4]: 6 a[2][5]: 4 a[3][0]: 6 a[3][1]: 0 a[3][2]: 5 a[3][3]: 0 a[3][4]: 0 a[3][5]: 2 a[4][0]: 0 a[4][1]: 3 a[4][2]: 6 a[4][3]: 0 a[4][4]: 0 a[4][5]: 6 a[5][0]: 0 a[5][1]: 0 a[5][2]: 4 a[5][3]: 2 a[5][4]: 6 a[5][5]: 0 The Minimal Spanning Tree Is : Edge (0 2 )and weight = 1 Edge (0 1 )and weight = 3 Edge (1 4 )and weight = 3 Edge (2 5 )and weight = 4 Edge (3 5 )and weight = 2 Total Path Length Is = 13 --------------------------------
0 comments: