1.程序实现的时候将点分成两部分,加入集合的和没有加入集合的;
2.每次从没有加入集合中找点;
3.对所有没有加入到集合中的点中,找一个边权最小的;
4.将边权最小的点加入集合中,并且修改和加入点相连的没有加入的点的权,重复第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
}
}
}