利用Prim（普里姆）算法 构造最小生成树 程序

算法同样是解决最小生成树的问题。

其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。

与prim算法的不同：prim算法为单源不断寻找连接的最短边掘亏雹，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。

复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。

Prim算法用于求无向图的最小生成树

设图G =（V，E），其生成树的顶点集合为U。

①、把v0放入U。

②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。

③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。

其算法的时间复杂度为O(n^2)

Prim算法实现：

（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对空悉应顶点不在集判帆合中（注意：顶点号与下标号差1）

（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。

{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}

Kruskal算法：

void Kruskal(Edge E[],int n,int e)

{

int i,j,m1,m2,sn1,sn2,k

int vset[MAXE]

for (i=0i<ni++) vset[i]=i//初始化辅助数组

k=1 //k表示当前构造最小生成树的第吵游几条边,初值为1

j=0 //E中边的下标,初值为0

while (k<n) //生成的边数小于n时循环

{

m1=E[j].um2=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=0i<ni++) //两个集合统一编号

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=0i<ni++) //给lowcost[]和closest[]置初值

{

lowcost[i]=g.edges[v][i]

closest[i]=v

}

for (i=1i<ni++) //找出n-1个顶点

{

min=INF

for (j=0j<nj++) //在(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=0j<nj++)//修改数组lowcost和closest

if (g.edges[k][j]!=0 &&g.edges[k][j]<lowcost[j])

{

lowcost[j]=g.edges[k][j]closest[j]=k

}

}

}

---