Pregunta: | 68286 - ARBOL DE EXPANSION MINIMA |
Autor: | Juan Robles |
Tengo el siguiente codigo, el cual quiero hacer con arbol de ezpansion minima, generar los vertices y el costo minimo, pero ya me atore a la hora de empezar a comparar los vertices, Si alguien me puede ayudar, se lo agradeceria. #include<stdio.h> #define n 6 #define inf 999 int prim(int costo[n][n],int t[n][2],int minicost); main(){ int a[n][n]={inf,10,inf,30,45,inf,10,inf,50,inf,40,25,inf,50,inf,inf,35,15,30,inf,inf,inf,inf,20,45,40,35,inf,inf,55,inf,25,15,20,55,inf}; int orden[n][2]={0},minicost=inf; minicost=prim(a,orden,minicost); printf("El orden a seguir es: "); for(int i=0;i<n;i++){ for(int j=0;j<2;j++){ printf(" %d a ",orden[i][j]);} printf(" ");} printf("El costo minimo es: %d",minicost); getchar(); getchar(); } int prim(int costo[n][n],int t[n][2],int minicost){ int near[n],i,j,k,l; for(i=0;i<n;i++) for(j=0;j<n;j++){ if(costo[i][j]<minicost){ minicost=costo[i][j]; k=i; l=j; } } t[k][0]=k; t[k][1]=l; for(i=0;i<n;i++){ if(costo[i][l]<costo[i][k]) near[i]=l; else near[i]=k; } for(int z=0;z<n;z++) printf(" %d",near[z]); near[k]=0; near[l]=0; for(i=1;i<n-1;i++){ for(j=0;j<n;j++){ if(near[j]!=0 && costo[j][near[j]]>costo[j][j]){ t[i][0]=j; t[i][1]=near[j]; minicost+=costo[j][near[j]]; near[j]=0; } } for(k=0;k<n;k++){ if(near[k]!=0 && costo[k][near[k]]>costo[k][j]) near[k]=j; } } return minicost; } |