Question

3. 最小生成树算法

Answer 1

在一给定的无向连通图 G = (V, E) 中， (u, v) 代表连接顶点 u 与顶点 v 的边， w(u, v) 代表此边的权重；若存在 T 为 E 的子集， G' = (V , T) 构成的图为 G 的生成树，使得的 ∑w(T) 最小，则此 T 为 G 的最小生成树。

最小生成树其实是最小权重生成树的简称。

在n个城市中建立一个通信网络，则连通这n个城市需要布置n-1一条通信线路，考虑如何在成本最低的情况下建立这个通信网？
于是可以引入连通图来解决上述问题，n个城市就是图上的n个顶点，然后，边表示两个城市的通信线路，每条边上的权重就是搭建这条线路所需要的成本，所以现在有n个顶点的连通网可以建立不同的生成树，每一颗生成树都可以作为一个通信网，当我们构造这个连通网所花的成本最小时，搭建该连通网的生成树，就称为最小生成树。

G＝ （V，E） 为一个带权连通无向图， U 是顶点集 V 的一个非空子集，若 （u，v） 是一条具有最小权的边，其中 u∈U ， v∈V-U ，则必存在一棵包含边 （u，v） 的最小生成树。

算法过程： 带权连通无向图 G＝ （V，E）

算法过程： 带权连通无向图 G＝ （V，E） ，Kruskal是 按权值递增顺序 选择 合适的边 来构造最小生成树的方法

最小生成树
Prim算法
Kruskal算法