什么是最小生成树

是一棵树

  • 无回路

  • v个顶点一定有v-1条边

是生成树

  • 包含全部顶点

  • v-1条边都在图里

边和权重都最小

Prim算法-让一棵小树长大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void Prim()
{
	MST={s};
	while(1){
	V= 未收录顶点中dist最小者;
	if( 这样的v不存在)
	break;
	将v收录进MST: dist[V]=0;
	for(V的每个邻接点w)
		if(dist[w]！=0)
			if(E(v,w)<dist[w]){
			dist[w]=E(v,w);
			parent[w]=v;
			}
	}
	if(MST中收到的顶点不到v个)
		Error("生成树不存在");
}

时间复杂度T=O（v^2)

Kruskal算法-将森林合并成树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Kruskal( Graph G)
{
	MST={ };
	while(MST中不到V-1条边&& E中还有边){
	从E中取一条权重最小的边E(v,w);
	将E(v,w)从E中删除;
	if(E(v,w)不在MST中构成回龙路)
		将E(v,w)加入MST;
	else
		彻底无视E(v,w);
	}
	if (MST中不到v-1条边)
		Error("生成树不存在");
	
}

时间复杂度 T=O（ElogE)

以上笔记来自于mooc中国大学数据结构浙江大学