7.5最小生成树

引用文章：图解：什么是最小生成树？ - 知乎 (zhihu.com)

7.5.1生成树的定义

一个连通图的生成树是一个极小的连通子图，它包含图中全部的n个顶点，但只有构成一棵树的n-1条边。

可以看到一个包含3个顶点的完全图可以产生3颗生成树。对于包含n个顶点的无向完全图最多包含 颗生成树。比如上图中包含3个顶点的无向完全图，生成树的个数为：

7.5.2生成树的属性

• 一个连通图可以有多个生成树；
• 一个连通图的所有生成树都包含相同的顶点个数和边数；
• 生成树当中不存在环；
• 移除生成树中的任意一条边都会导致图的不连通， 生成树的边最少特性；
• 在生成树中添加一条边会构成环。
• 对于包含n个顶点的连通图，生成树包含n个顶点和n-1条边；
• 对于包含n个顶点的无向完全图最多包含 颗生成树。 颗生成树。

生成树我们知道了，下面我们来看看最小生成树

所谓一个 带权图 的最小生成树，就是原图中边的权值最小的生成树

通过定义我们知道，最小生成树其实是和带权图联系到一起的，如果是非带权图，那他们只存在生成树，我们来看看例子

上图中，原来的带权图可以生成左侧的两个最小生成树，这两颗最小生成树的权值之和最小，且包含原图中的所有顶点。

那么如何从图中得到最小生成树呢？

最小生成树算法有很多，其中最经典的就是克鲁斯卡尔（Kruskal）算法和 普里姆（Prim）算法，也是我们考试、面试当中经常遇到的两个算法。