4.用Prim算法求下图的最小生成树, 若从顶点0出发,请将算法中的两个辅助数组的变化过程填入下表。

来源:百度知道 编辑:UC知道 时间:2024/06/14 02:19:19
4.用Prim算法求下图的最小生成树, 若从顶点0出发,请将算法中的两个辅助数组的变化过程填入下表。
郁闷,好像没办法连6/7条边
走到6就卡住了,之前一直都是严格按照prim算法按小的走

不好意思吖按照图弄那两个中间数组太久了。。。实现方法也有不同。我跟您说说我学的通用实现方法吧!
点集合:A,代表已经扩展到的点。
边集合B:代表待考虑的边,一开始为空。
一开始从任意点出发,如0.此时集合A中只有点0。将和A相邻的所有边加入到B中。
从B中选最短的一条边e。e的一个端点必不在A中,则将它加入A中。将不在A中的那个点的所有边加入B中,在B中删除边e
这样B中减少了一条边(先前的边中最短的)。在A中增加了一个新点,并且这个点的相关边加入了B中。而B中减少的这条边就是最小生成树的一条边。
这样一来,调用以上两个步骤N-1次(有N个点),则可以得到n-1条线段,就是其最小生成树。
如果不是很懂可以Q我,我会用通俗的语言解释的^^
QQ:328880142