最小生成树的定义:最小生成树是一副连通加权无向图中一棵权值最小的生成树。
假设给定无向图G一共有n个顶点,那么最小生成树一定会有n-1条边
prim算法被用来求给定图的最小生成树
具体内容:
用两个集合A{},B{}分别表示找到的点集,和未找到的点集;我们以A中的点为起点a,在B中找一个点为终点b,这两个点构成的边(a,b)的权值是其余边中最小的 重复上述步骤#2,直至B中的点集为空,A中的点集为满
举例说明:
默认从第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
思考过程记录: