最小生成树

生成树的概念

        在一个任意连通图G中，如果取它的全部顶点和一部分边构成一个子图G'，即：V（G'）=V（G）和E（G'）⊆E（G）

        若同时满足边集E（G'）中的所有边既能够使全部顶点连通而又不形成任何回路，则称子图G'是原图G的一棵生成树。

        下面简单说明一下，在既能够连通图G中的全部n个顶点又没有形成回路的子图G'（即生成树）中，必定包含n-1条边。要构造子图G'，首先从图G中任取一个顶点加入G'中，此时G'中只有一个顶点，假定具有一个顶点的图是连通的，以后每向G'中加入一个顶点，都要加入以该顶点为一个端点（终点），以已连通的顶点之中的任一个顶点为开始顶点的一条边，这样既连通了该顶点又不会产生回路，进行n-1次后，就向G'中加入了n-1个顶点和n-1条边，使得G'中的n个顶点既连通又不产生回路。

       在图G的一棵生成树G'中，若再增加一条边，就会出现一条回路。这是因为此边的两个端点已连通，再加入此边后，这两个端点间有两条路径，因此就形成了一条回路，子图G'也就不再是生成树了。同样，若从生成树G'中删去一条边，就使得G'变为非连通图。这是因为此边的两个端点是靠此边唯一连通的，删除此边后，必定使这两个端点分属于两个连通分量中，使G'变成了具有两个两通分量的非连通图。

        同一个连通图可以有不同的生成树。例如对于图9-1（a），其余3个子图都是它的生成树。在每棵生成树中都包含8个顶点和7条边，即n个顶点和n-1条边，此时n等于原图中的顶点数8，它们的差别只是边的选取方法不同。

       在这3棵生成树中，图9-1（b）中的边集是从图9-1（a）中的顶点V0出发，利用深度优先搜索遍历的方法而得到的边集，此图是原图的深度优先生成树；图9-1（c）中的边集是从图9-1（a）中的顶点V0出发，利用广度优先搜索遍历的方法而得到的边集，此图是原图的广度优先生成树；图9-1（d）是原图的任意一棵生成树。当然图9-1（a）的生成树远不止这3种，只要能连通所有顶点而又不产生回路的任何子图都是它的生成树。

       对于一个连通网（即连通带权图，假定每条边上的权值均为正实数）来说，生成树不同，每棵树的权（即树中所有边上的权值总和）也可能不同。图9-2（a）就是一个连通网，图9-2（b）、（c）和（d）是它的3棵生成树，每棵树的权各不相同。它们分别为57、53和38.具有权值最小的生成树被称为图的最小生成树。通过后面将要介绍的构造最小生成树的方法可知，图9-2（d）是图9-2（a）的最小生成树。

最小生成树是在一个给定的无向图G（V,E）中求一棵树T

使得这棵树拥有图G中的所有顶点

且所有边都是来自图G中的边

并且满足整棵树的边权之和最小

【性质】

① 最小生成树是树，因此其边数等于顶点数减1，且树中一定不会有环

②对给定的图G但其（V,E），其最小生成树可以不唯一，但其边权之和一定是唯一的

③由于最小生成树是在无向图上生成的，因此其根结点可以是这棵树上的任何一个结点

一般求解最小生成树有两种算法

即prim算法和kruskal算法

https://blog.csdn.net/weixin_43272781/article/details/83589373
https://blog.csdn.net/weixin_43272781/article/details/83589394