二十五、最小生成树

一、最小生成树及其性质

最小生成树（Minimum (Cost) Spanning Tree）是在一个给定的无向图 $G(V,E)$ 中求一棵树 $T$，使得这棵树拥有图 $G$ 中的所有顶点，且所有边都是来自图G中的边，并且满足整棵树的边权之和最小。

离散数学上的定义为：连通加权图里的最小生成树是具有边的权之和最小的生成树。

最小生成树有三个性质需要掌握：

1. 最小生成树是树，因此其边数等于顶点数减1，且树内一定不会有环。
2. 对给定的图 $G(V,E)$ ，其最小生成树可以不唯一，但其边权之和一定是唯一的。
3. 由于最小生成树是在无向图上生成的，因此其根节点可以是这棵树上的任意一个结点。

二、最小生成树算法

1.普林（Prim）算法

考试不考具体算法，在这里给出伪代码，展示思路

procedure Prim(G:带n个顶点的连通加权无向图)
T:=权最小的边
for i:=1 to n-2
	e:=与T里顶点关联且若添加到T里则不形成简单回路的权最小的边
	T:=添加e之后的T
return T{T是G的最小生成树}

//G为图，一般设成全局变量；数组d为顶点与集合S的最短距离
Prim( G, d[] )
{
	初始化;
	for( 循环n次 )
	{
		u = 使d[u]最小的还未被访问的顶点的标号;
		记u已被访问;
		for( 从u出发能到达的所有顶点v )
		{
			if( v未被访问 && 以u为中介点使得v与集合S的最短路径d[v]更优 )
			{
				将G[u][v]赋值给v与集合S的最短距离d[v];
			}
		}
	}
}

动图演示：

非动图演示：