最小生成树

5,return A

一开始A为P，显然满足最小生成树子集的条件。之后，每一次循环把一条A的安全边加入A中，A依然是最小生成树。确认安全边的规则由下列定理得到，设图G(V,E)是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的一个子集，且包含于G的某个最小生成树中，割（S,V-S）是G的不妨碍A的任意割且边（u,v）是穿过割（S,V-S）的一条轻边，则边(u,v)对集合A是安全的。其中有一个推论也很有用，设G=（V,E）是一无向连通图，且在E上定义了相应的实数值加权函数w，设A是E的子集且包含于G的某个生成树中，C是森林Ga=(V,A)中的连通支。若边（u,v）是连接C和Ga中其他某连通支的一轻边，则边(u,v)对集合A是安全的。那么如何很好地实现最小生成树的算法和应用就显得尤为重要。

最小生成树的应用相当广泛，比如在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只用n-1根电线就可以了把问题转化为图论模型就是：一个无向连通图G=（V,E）,V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边（u，v）一个权值w（u，v），表示连接它们所需要的电线长度。我们的目标就是找到一个无环的边集T，连接其中所有的点且使总权值最小。总权值w（T）=w（u，v），既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是生成出来的，便被称为生成树，如果一棵树中总权值最小，它就是最小生成树。其中一个典型应用就是基于最小生成树算法的网架规划