最小生成树之Prime法

关于最小生成树的概念，在前一篇文章中已经讲到，就不在赘述了。下面介绍Prime算法：

其基本思想为：从一个顶点出发，选择由该顶点出发的最小权值边，并将该边的另一个顶点包含进来，然后找出由这两个顶点出发的最小边，依此类推，直至包含所有的顶点。如果期间构成环，就舍弃该边，继续寻找最小边。下面以具体实例来说明算法的过程：

具体的程序实现如下：

< http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHByZSBjbGFzcz0="brush:java;">#include #define N 6 //顶点数 #define MAX 10000 typedef struct { int startvex,endvex;//边的起点和终点2 int length;//边的权值 }edge; int flag[N]={0};//标志顶点是否被选定 int flag1=0;//记录边的终点 int flag2=0;//记录边的起点 void Prime(int i,int dist[N][N],edge T[N-1]) { int j,k,min; int num=0; flag[i]=1;//包含顶点置为1 while(num<5)//6个顶点则有5条边 { min=MAX; for(j=0;j
运行结果如下：

注意最小生成树不是唯一的，但是总权值是一样的。

注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接： 解释说明