最小生成树－kruskal算法.txt

数据结构C对图的操作算法

void minitree_KRUSKAL(void)
{   int n,i,m,min,k,j;
    VEX t[M];
    EDGE  e[M];

    printf("Input number of vertex and edge:");
    scanf("%d,%d",&n,&m);
    for(i=1;i<=n;i++)
    {   printf("t[%d].data=:",i);
	scanf("%d",&t[i].data);
	t[i].jihe=i;
    }//建立结点数组t[n]

    for(i=0;i<m;i++)
    {   printf("vexh,vext,weight:");
	scanf("%d,%d,%d",&e[i].vexh,&e[i].vext,&e[i].weight);
	e[i].flag=0;
    } //建立边数组e[m]


    i=1;
    while(i<n) //n为结点数，而生成树有n-1条边
    {   min=MAX;
	for(j=0;j<m;j++) //m为边数
	{  if(e[j].weight<min && e[j].flag==0)
	   {   min=e[j].weight;
	       k=j;
	   }
	}查找未被处理的权值最小的边在边数组e中的下标并存于k

	if(t[e[k].vexh].jihe!=t[e[k].vext].jihe)//如果对应的顶点不属于同一个集合
	{    e[k].flag=1; //表示选中这条边
	     for(j=1;j<=n;j++)
		if(t[j].jihe==t[e[k].vext].jihe)
		   t[j].jihe=t[e[k].vexh].jihe;
	     t[e[k].vext].jihe=t[e[k].vexh].jihe;//集合域置为相同值	     
	}
	else //如果对应的顶点属于同一个集合
	   e[k].flag=2;//表示舍去这条边

       i++; //继续查找下一个最小权值
    }

    for(i=0;i<m;i++)//输出最小生成树的顶点和边
       if(e[i].flag==1)
	 printf("%d,%d :%d\n",e[i].vexh,e[i].vext,e[i].weight);
}