最小生成树问题中Kruskal算法和Prim算法的C语言实现

 Kruskal算法：

void Kruskal(Edge E[],int n,int e)
{
 int i,j,m1,m2,sn1,sn2,k;
 int vset[MAXE];
 for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
 k=1;                    //k表示当前构造最小生成树的第几条边,初值为1
 j=0;                    //E中边的下标,初值为0
 while (k<n)           //生成的边数小于n时循环
 { 
   m1=E[j].u;m2=E[j].v;        //取一条边的头尾顶点
  sn1=vset[m1];sn2=vset[m2];  //分别得到两个顶点所属的集合编号
  if (sn1!=sn2)        //两顶点属于不同的集合,该边是最小生成树的一条边
  { 
    printf("  (%d,%d):%d/n",m1,m2,E[j].w);
    k++;                    //生成边数增1
    for (i=0;i<n;i++)       //两个集合统一编号
     if (vset[i]==sn2)   //集合编号为sn2的改为sn1
             vset[i]=sn1;
  }
  j++;         //扫描下一条边
 }
}

Prim算法：
void prim(MGraph g,int v)
{
 int lowcost[MAXV],min,n=g.vexnum;
 int closest[MAXV],i,j,k;
 for (i=0;i<n;i++)           //给lowcost[]和closest[]置初值
 { 
  lowcost[i]=g.edges[v][i];
  closest[i]=v;
 }
 for (i=1;i<n;i++)           //找出n-1个顶点
 {   
  min=INF;
     for (j=0;j<n;j++)       //在(V-U)中找出离U最近的顶点k
      if (lowcost[j]!=0 && lowcost[j]<min) 
   { 
    min=lowcost[j];k=j;  
   }
  printf("  边(%d,%d)权为:%d/n",closest[k],k,min);
  lowcost[k]=0;          //标记k已经加入U
  for (j=0;j<n;j++)    //修改数组lowcost和closest
            if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j]) 
   { 
    lowcost[j]=g.edges[k][j];closest[j]=k; 
   }
 }
}

【程序系转载，稍加编辑，出处详见http://zhidao.baidu.com/question/155997031.html】
 
 
蚊子小结：
　　Krustal算法的运行时间取决于不相交集合数据结构是如何实现的。上述程序使用数组实现不相交集合数据结构，思路简单，但耗时相对较长。另一种实现不相交集合数据结构的方法是采用有根数，在实践上可以到达线性的运行时间。
　　Prim算法的运行时间取决于优先队列是如何实现的。如果用二叉最小堆来实现，Prim算法需要O(ElgV)时间，若改用斐波那契堆，则可以将运行时间改进到O(E+VlgV)。