6-1 最小生成树(普里姆算法)
试实现普里姆最小生成树算法。
函数接口定义:
void Prim(AMGraph G, char u);
其中 G
是基于邻接矩阵存储表示的无向图,u
表示起点
void Prim( AMGraph G, char v )
{
int distance[G.vexnum];
int parent[G.vexnum];
//记录v的下标
int index=0;
int i,min=MaxInt,imin,count=0;
// 1.初始化这棵树,即以v为起始点,同时初始化数组distance[]
// 注:distance数组表示该树的任意一点到该点的最小距离
//寻找v的下标
for (i = 0; i < G.vexnum; i++)
{
if (G.vexs[i]==v)
{
index=i;
}
}
for (i = 0; i < G.vexnum; i++)
{
if (i==index)
{
distance[i]=0;
parent[i]=index;
}else
{
distance[i]=G.arcs[index][i];
parent[i]=index;
}
}
while (1)
{
if (count==G.vexnum-1)
{
break;
}
// 2.从小树现有的结点出发,寻找边权值最小的点:
for ( i = 0; i < G.vexnum; i++){
if (min>distance[i]&&distance[i]!=0)
{
//记录最小值及其下标
min=distance[i];
imin=i;
}
}
//更新已到达过得节点数
count++;
// 3.找到后输出该边
if (count<G.vexnum-1)
{
printf("%c->%c\n",G.vexs[parent[imin]],G.vexs[imin]);
}else
{
printf("%c->%c",G.vexs[parent[imin]],G.vexs[imin]);
}
//初始化min以便下次寻找
min=MaxInt;
// 4.将该点的distance数组中的值赋值为0,标记已经遍历过
distance[imin]=0;
// 5.循环遍历结点,更新distance[]数组
for ( i = 0; i < G.vexnum; i++){
if (distance[i]!=0&&G.arcs[i][imin]<MaxInt)
{
if (distance[i]>G.arcs[i][imin])
{
distance[i]=G.arcs[i][imin];
parent[i]=imin;
}
}
}
}
}