2 zq741552720 ZQ741552720 于 2015.06.24 18:07 提问

kruscal 求最小树 问题求大神

图片说明
对图中的图 求出她所有的最小二叉树图中有2棵最小树 要求用kruscal 算法

我想到的是 要在排序函数中产生2 组排序 1 2 3 4 4 * 5
1 2 3 4* 4 5 我用的是选择排序 但没弄出来 求大神给指导下 谢谢
void kruskal(mgraph g)
{
int i,j;
int k;
int u1,v1,sn1,sn2;
edge e1[MS]; //边权值列表
int vset[MS]; //顶点链接判断列表

k=0;
for(i=0;i<g.d;i++)     //边权值列表初始化  
{
   for(j=0;j<g.d;j++)
   if(g.edges[i][j]!=0&&g.edges[i][j]!=inf)
   {
    e1[k].q=i; e1[k].z=j; e1[k].w=g.edges[i][j];
    k++; 
   }
} 

 //对 edga 进行排序 (从小到大) 
 sort(e1,k);

 for(i=0;i<g.d;i++)     //初始化辅助数组 
    vset[i]=i;

 k=1;      
 j=0;
 while(k<g.d)
 {
    u1=e1[j].q; v1=e1[j].z;
    sn1=vset[u1]; sn2=vset[v1];

    if(sn1!=sn2)
    {
        printf("边(%d,%d)权为:%d \n",sn1,sn2,e1[j].w);
        k++;
        for(i=0;i<g.d;i++)     //归 sn1 和 sn2 与一个数组  
           if(vset[i]==sn2)
              vset[i]=sn1;
    }
    j++;
 } 

}

//选择排序
void sort(edge e1[MS],int b)
{
int i,j;
int k;
edge tomp;

for(i=0;i<b;i++)
{
    k=i;
    for(j=i;j<b;j++)
    {
        if(e1[k].w>e1[j].w)
        k=j;
    }
    tomp=e1[k];
    e1[k]=e1[i];
    e1[i]=tomp;
}

}
求大哥大姐 帮帮忙 看下要怎样改!!!!!

3个回答

ZQ741552720
ZQ741552720   2015.06.24 18:18

图片说明

ZQ741552720
ZQ741552720   2015.06.24 19:13

有人没 哪位给说下啊

u011877621
u011877621   2015.06.25 00:10
Csdn user default icon
上传中...
上传图片
插入图片