kruskal.c

里面包含各种数据结构方面的知识,如链表,树,图等 含有vc代码

#define MAXEDGE 50

typedef int elemtype;

typedef struct
{
   elemtype v1;
   elemtype v2;
   int    Cost;
} edgetype;

int Find(int father[],int e);

void Kruskal(edgetype Edges[],int n)
/* 用克鲁斯卡尔方法构造有n个顶点的图Edges的最小生成树。*/
{
   int Father[MAXEDGE];
   int i, vf1, vf2;

   for(i = 0;i < n;i ++) Father[i] = 0;
   for(i = 0;i < n;i ++)
   {
      vf1 = Find(Father,Edges[i].v1);
      vf2 = Find(Father,Edges[i].v2);
      if(vf1 != vf2)
      {
	 Father[vf2] = vf1;
	 printf("%5d%5d\n",Edges[i].v1, Edges[i].v2);
      }
   }
}

int Find(int Father[],int v)
/* 寻找顶点v所在树的根结点 */
{
   int t;

   t = v;
   while(Father[t] > 0)
      t = Father[t];
   return(t);
}

void InputEdge(edgetype Edges[],int n)
{
   int i;
   int v1,v2,w;

   printf("\nInput v1 & v2 & data:\n");
   for(i = 0;i < n;i ++)
   {
      scanf("%d%d%d",&v1,&v2,&w);
      Edges[i].v1   = v1;
      Edges[i].v2   = v2;
      Edges[i].Cost = w;
   }
}

main()
{
   edgetype Edges[MAXEDGE];
   int n, i, j;

   printf("\nInput the edges number:\n");
   scanf("%d",&n);

   InputEdge(Edges,n);

   Kruskal(Edges,n);

}