用于得到最小生成树
时间复杂度:o(n2)
概念梳理:
- 需要选择一个点作为起点
- 使用贪心的原则选择下一个点
- 使用优先队列(待补充)
- 针对无向图
- 适用于稠密图
算法需要:
所有边的长度(邻接矩阵即可)
数组dist[],用来存放当前最小生成树到其他没有被纳入最小生成树的点的最短距离
数组set[],用来存放点是否被纳入最小生成树中
描述下步骤:
初始化:
我们以0点作为起点,最开始dist初始化为从0点到其他点的距离,譬如dist[1]就表示起点0到点1的距离。
set[i]置1表示i点被纳入最小生成树中了,所以初始化时,set[0]置1,其他位置0。
用sum来记录最小生成树的权值。
循环:
可以推知,在n个点的情况下,经过初始化以后,我们还需要执行n-1次才能完成将所有点都纳入最小生成树,所以总的循环为n-1次。
循环内做什么呢?
- 找到没有被纳入集合的dist数组中数值最小的点i,这里我用一个变量min来记录点i,将其纳入集合(set[min]置1),sum值更新为sum+dist[i]。
- 以当前的min点为起点,更新所有没有被纳入最小生成树的点j的dist[j],具体的更新方法为:当dist[j]>边[min][j]时,更新dist[j]为边[min][j]的值。
循环n-1次后,算法完成。
总结:算法实现很巧妙,理解了就很简单,个人觉得还是需要去用心理解。