无权无向图,只给出节点个数,怎么用Prim算法求最小生成树
来源：学生作业帮助网 编辑：六六作业网 时间：2025/02/07 14:49:29
无权无向图,只给出节点个数,怎么用Prim算法求最小生成树
无权无向图,只给出节点个数,怎么用Prim算法求最小生成树
无权无向图,只给出节点个数,怎么用Prim算法求最小生成树
Prim算法的主要运行时间花在过程②的选边中.看起来复杂度是O(VE)=O(V^3)不是么,效率也太低了吧……
为了比较快速地选边,我们用两个数组lowcost、closest动态地维护每一个点到S的最短距离.在某一状态下,lowcost[i]表示所有与i相连且另一端点在S中的边中的权值最小值,closest[i]表示在S中且与i相连的点中与i之间距离最小的点.显然,lowcost[i]=w(i,closest[i]).需要注意的是两个数组记录的都是边而不是路径.若i没有边直接连向S,则lowcost[i]=∞.另外,若i已在S中,则lowcost[i]=0.
设出发点为x.初始时对于任意k∈V,closest[k]=x,lowcost[k]=w（k,x）【w（i,j）表示i、j间的距离.初始化时,若两点间没有边则w（i,j）赋为一个足够大的整数（如maxint）,并且所有点到自身的距离赋为0,即w（i,i）=0】
每一次找出lowcost中不为0的最小值lowcost[i],然后把i加入S（即lowcost[i]:=0）,然后对于图中所有点k,若w(k,i)
以上操作重复|V|-1次结束.由于每次加入S的点i都在当时取到了符合流程②的边min{lowcost},而lowcost[i]=w(i,closest[i]),所以此时的最小生成树的各边就是(i,closest[i]),i∈V且not (i=x)【需要注意的是出发点x的closest[x]还是x,所以应忽略,实际取到x-1条边】.把i从1取到|V|,便得到最小生成树T的每条边.
程序：
for(k= 1;k <= n; k++){ //x为S中的第一个点,x任选一个都可
lowcost[k] = w[x][k]; //lowcost表示k点到前集合的最小值,是k与前集合中的closet[k]间的距离
closest[k] = x;
} //初始化
for(i = 2; i <= n; i++){ //除去x,还要加入n – 1个点
temp = maxint;
for(j = 1; j <= n; j++)
if(lowcost[j] < temp && lowcost[j] != 0) {
temp = lowcost[j];
k = j;
} //找出S外距S最近的点k
lowcost[k] = 0; //将k加入生成树
for(j = 1; j <= n; j++)
if(w[k][j] < lowcost[j]){
lowcost[j] = w[k][j];
closest[j] = k;
} //由新加入S中的k点使某些点到S的距离缩短,所以更新各点的lowcost和closest,即再次初始化
}
for(i = 1; i <= n; i++)
if(i != closest[i]){
printf(“%d %d”, i, closest[i]);
} //输出最小生成树的各边
不难看出,以上算法包含一个二重循环,算法复杂度为O（V^2）,与图的稠密度无关