图的最小代价生成树以

时间:2021-04-16 11:37:05

求图的最小代价生成树以及按边的大小排序。

#include<stdio.h>
#include<stdlib.h>
typedef struct edge{
int start;
int end;
int pr;
}Edge;
int a[5][5]={{0,1,0,2,2},
     {1,0,2,0,0},
     {0,2,0,3,4},
     {2,0,3,0,0},
     {2,0,4,0,0}};
void copyEdge(Edge* a,Edge* b){
    a->start=b->start;
    a->end=b->end;
    a->pr=b->pr;
}
int minnear(int a[][5],int *p,int len){
    int i=0,min=50,minindex;
    for(i=0;i<len;i++){
        if(p[i]!=-1){
            if(a[i][p[i]]<min){min=a[i][p[i]];minindex=i;}
        }
    }
    return minindex;
}
int main(void){
    int i=0,j=0,count=0;
    Edge * edges=NULL;
    Edge t;
    for(i=0;i<5;i++){
        for(j=0;j<5;j++){
            if(a[i][j]!=0){
                count++;
                edges=(Edge*)realloc(edges,count*sizeof(Edge));
                edges[count-1].start=i;
                edges[count-1].end=j;
                edges[count-1].pr=a[i][j];
            }
        }
    }
    for(i=1;i<count;i++){
        j=i-1;t=edges[i];
        while((j>=0)&&(edges[j].pr>t.pr)){
            copyEdge(&edges[j+1],&edges[j]);
            j--;
        }
        copyEdge(&edges[j+1],&t);
    }
    for(i=0;i<count;i++){
        printf("%d--%d==%d\n",edges[i].start,edges[i].end,edges[i].pr);
    }


    //最小代价生成树
    //假设从第一点开始进行最小代价生成树的生成
    int near[5];
    int min=50,s,e;
    int minindex[4][2];
    for(i=0;i<5;i++){
            for(j=0;j<5;j++){
                if(min>a[i][j]&&a[i][j]!=0){
                    s=i;e=j;min=a[i][j];
                }
            }
    }
    int k;
    minindex[0][0]=s;
    minindex[0][1]=e;
    for(i=0;i<5;i++){
        if(a[s][i]!=0&&a[i][e]!=0){
        if(a[s][i]<a[i][e])near[i]=s;
        else{near[i]=e;}
        }else if(a[s][i]==0&&a[i][e]!=0){
        near[i]=e;
        }else if(a[s][i]!=0&&a[i][e]==0){
        near[i]=s;
        }else{
        near[i]=-1;
        }
    }

    near[s]=-1;near[e]=-1;
    for(i=1;i<4;i++){
        j=minnear(a,near,5);
        minindex[i][0]=j;minindex[i][1]=near[j];
        near[j]=-1;
        for(k=0;k<5;k++){
            if(near[j]!=-1){
                if(a[k][j]<a[k][near[k]]&&a[k][j]!=0){
                    near[k]=j;
                }
            }
        }
    }
    for(i=0;i<4;i++){
        printf("%d---%d\n",minindex[i][0],minindex[i][1]);
    }
return 0;
}