最小生成树（Kruskal算法和Prim算法）-JZTXT

关于图的几个概念定义：

连通图：在无向图中，若任意两个顶点v_i $v_{i}$
强连通图：在有向图中，若任意两个顶点 $v_{i}$
连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权；权代表着连接连个顶点的代价，称这种连通图叫做连通网。
生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。一颗有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环。
最小生成树：在连通网的所有生成树中，所有边的代价和最小的生成树，称为最小生成树。

1.介绍

此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

2.算法分析

假若以“堆”结构来存放边进行堆排序，对于包含 e 条边的网，上述算法排序的时间复杂度为 O(e㏒₂e)。只要采取合适的数据结构，算法的时间复杂度为 O(e㏒₂e)。与普里姆算法相比，该算法更适合于求稀疏图的最小生成树。

1.算法介绍

此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点s开始，逐渐长大覆盖整个连通网的所有顶点。

2.算法分析

该算法时间复杂度为 O(n²)，与图结构的边数无关，适合稠密图。（n是点的数量）