1 最小生成树的概念

最小生成树的概念：是由图生成而来的

是一棵树

1.无回路

2.如果有V个定点就有V-1条边

是生成树

1.包含图中所有的节点V

2.V-1条边都在图里面

3.边的权重和最小。

4.向生成树中添加任意一条边都构成回路。

2 算法思想：贪心算法

“贪”:每一步都要最好的。

“好”：权重最小的边

约束条件:

1.只能使用图里面的边

2.只能正好使用V-1条边

3.不能有回路

3 Prim算法—让一棵小树慢慢长大

3.1算法思想：

1.先选择一个顶点作为树的根节点，把这个根节点当成一棵树

2.选择图中距离这棵树最近但是没有被树收录的一个顶点，把他收录在树中，并且保证不构成回路

3.按照这样的方法，把所有的图的顶点一一收录进树中。

4.如果没有顶点可以收录

a.如果图中的顶点数量等于树的顶点数量-->最小生成树构造完成

b. 如果图中的顶点数量不等于树的顶点数量-->此图不连通

下面使用图片来具体描述此算法的算法思想：

 3.2Prim算法的伪代码描述

通过我们对算法的描述，我们发现Prim算法和Dijkstra算法很类似

void Prim()

{

MST = {s};

while (1) {

V = 未收录顶点中dist最小者;

if ( 这样的V不存在 )

break;

将V收录进MST: dist[V] = 0;

for ( V 的每个邻接点 W )

if ( dist[W]!=W未被收录 0 )

if ( E (V,W) < dist[W] ){

dist[W] = E (V,W) ;

parent[W] = V;

}

}

if ( MST中收的顶点不到|V|个 )

Error ( “生成树不存在” );

}

对于Prim算法

1.dist代表的是什么，应该如何被初始化

dist代表距离当前生成树的最小距离。和根节点直接相邻的初始化为权重，其他的初始化为正无穷。等每插入一个树节点，对dist进行更新。对于已经收录的节点，更新其dist=0

2.该算法的时间复杂度是多少

该算法时间复杂度在于如何去 ”未收录顶点中dist最小者”如果是使用暴力搜索的方法，那么时间复杂的为T=O(n^2).此种算法对于稠密图比较适用。

最小生成树之Prim算法