Tata: Created page with "

 #include #define infi 999999 int mat[10000][10000],v,e,sel[10000],pass[10000],parent[10000]; int main(){     printf("Enter number of vertex and edge : ");     s..."

2019-03-07T17:12:53Z

Created page with "<pre> #include<stdio.h> #define infi 999999 int mat[10000][10000],v,e,sel[10000],pass[10000],parent[10000]; int main(){ printf("Enter number of vertex and edge : "); s..."

New page

<pre>
#include<stdio.h>
#define infi 999999
int mat[10000][10000],v,e,sel[10000],pass[10000],parent[10000];
int main(){
printf("Enter number of vertex and edge : ");
scanf("%d%d",&v,&e);
int i,j,from,to,weight;
for(i=0;i<=v;i++){
for(j=0;j<=v;j++){
mat[i][j]=infi;
}
sel[i]=infi;
}
printf("Enter edge Format (start end weight) : \n");
for(i=0;i<e;i++){
scanf("%d%d%d",&from,&to,&weight);
mat[from][to]=weight;
mat[to][from]=weight;
}
int numpass,min=0,sum=0;
sel[1]=0;
for(i=1,numpass=0;numpass<v;numpass++){
//printf("%d ",i);
pass[i]=1;
sum+=sel[i];
min=0;
for(j=1;j<=v;j++){
if(pass[j]==1||j==i) continue;
if(mat[i][j]<sel[j]){
sel[j]=mat[i][j];
parent[j]=i;
}
if(sel[j]<sel[min]) min=j;
}
i=min;
}
printf("\nMinimum Spanning Tree cost : %d\n",sum);
for(i=2;i<=v;i++){
printf("%d %d %d\n",parent[i],i,sel[i]);
}

scanf(" ");
return 0;
}
/*
6 9
1 2 4
1 3 2
1 5 3
2 4 5
3 4 1
3 5 6
3 6 3
4 6 6
5 6 2

12 20
1 2 3
1 3 5
1 4 4
2 5 3
2 6 6
3 4 2
4 5 1
5 6 2
3 7 4
4 8 5
5 9 4
6 10 5
7 8 3
8 9 6
9 10 3
7 11 6
8 11 7
9 12 5
10 12 9
11 12 8
*/
</pre>

Prim Algorithm - Revision history

Tata: Created page with "
#include #define infi 999999 int mat[10000][10000],v,e,sel[10000],pass[10000],parent[10000]; int main(){ printf("Enter number of vertex and edge : "); s..."