700字范文,内容丰富有趣,生活中的好帮手!
700字范文 > prim算法_Prim算法——最小生成树

prim算法_Prim算法——最小生成树

时间:2023-12-15 03:28:18

相关推荐

prim算法_Prim算法——最小生成树

最小生成树的定义:最小生成树是一副连通加权无向图中一棵权值最小的生成树。

来自维基百科的定义

假设给定无向图G一共有n个顶点,那么最小生成树一定会有n-1条边

prim算法被用来求给定图的最小生成树

具体内容:

用两个集合A{},B{}分别表示找到的点集,和未找到的点集;我们以A中的点为起点a,在B中找一个点为终点b,这两个点构成的边(a,b)的权值是其余边中最小的 重复上述步骤#2,直至B中的点集为空,A中的点集为满

举例说明:

图1

默认从第0个点开始,初始时A{0},B{1,2,3,4,5}

lowcost{m,6,1,5,m,m} #lowcost表示当前A到B中的点的最低权值,m表示不能到达

可以看出,权值 1 最小,所以选择顶点 2 ,更新A{0,2},B{1,3,4,5}

此时因为加入了顶点2,lowcost就可以更新了

lost cost{m,5,m,5,6,4}

权值 4 最小,所以选择顶点5,更新A{0,2,5},B{1,3,4}

更新low cost {m,5,m,2,6,m}

权值2最小,所以选择顶点3,更新A{0,2,5,3},B{1,4}

更新lowcost {m,5,m,m,6,m}

权值 5 最小,所以选择顶点1,更新A{0,2,5,3,1},B{4}

更新low cost {m,m,m,m,3,m}

权值 3 最小,选择顶点4,更新A{0,2,5,3,1,4},B{}

lowcost {m,m,m,m,m,m}

OK,B为空,A为满,满足终止条件,结束寻找。

python代码实现

import

代码输出:

总结:

碰到的bug是在输出每条边的起始点出了问题,当时没有考虑其他的,直接把更新之前的点作为起点,更新之后的点作为终点,没有考虑如果在将要生成环时,起始点会重新选择。

于是在参考了网上的博客,用一个数组mst记录每次更新权值时的当前点,(权值因为这个添加了这个点才被更新,所以在后面如果选择了这个权值,那么这个点一定是该权值对应边的起点)

代码下载:

/TwoAndOne/Algorithm-Design-and-Analysis-Course-for-Related-Algorithm-Learning-/tree/master​

思考过程记录:

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。