生成树的概念

• 若图是连通的无向图或强连通的有向图，则从其中任一顶点出发，调用一次$dfs$或者$bfs$后，可以系统的访问图中所有顶点。
• 若图是有根的有向图 ，则从根出发，调用一次$dfs$或者$bfs$后，可以系统的访问图中所有顶点。

在上述情况之下，图中所有顶点加上遍历过程中经过的所有边所构成的子图称为原图的生成树。

若图是不连通的的无向图和不是强连通的有向图，从其中任一顶点出发，调用一次$dfs$或者$bfs$后，不能系统的访问图中所有顶点，只能得到以出发点为根的连通分支（或者强连通分支）的生成树。若想访问其他顶点则需要以一个没有访问过的点作为起点，再次调用$dfs$或者$bfs$，这样就得到了生成森林。

很显然，一个图的生成树并不是唯一的，不同的搜索方法或者同一个搜索方法但出发点不同，都可以得到不同的生成树。
可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。

最小生成树算法

举例：给出一张有五座城市的地图。

用DFS遍历得到的生成树：

用BFS遍历得到的生成树：

上述俩种生成树的权和分别为20和33，我们不难发现，最小的生成树权和应该为19，因此上述俩种并不是最小生成树。那如何得到最小生成树呢？

出发点：具有n个顶点的带权连通图，其对应的最小生成树都有n-1条边。
下列俩种算法都是基于贪心思想的算法。
时间复杂都为O(n*n)。

Prim算法

思路如下：

1. 设置一个顶点集合S和一个边集合TE，S和TE的初始状态皆为空集。
2. 选定图中的任意顶点K，从K开始生成最小生成树。(K加入集合S)。
3. 重复下列操作，直到选取了n-1条边为止。
   (1)选取一条权最小的边(X，Y)，要求是X要是集合S的元素，Y不是集合S的元素。
   (2)将顶点加入到集合S中，将边（X，Y）加入集合TE中。
4. 得到最小生成树T，T=（S，TE）。

Kruskal算法

思路如下：

1. 设最小生成树为T，T=（S，TE），TE初始状态为空集。
2. 将图中的边权从小到大依次排序。
3. 选取权最小的边，若这条边没有使T构成回路，就将这条边加入TE中（T保留了这条边）；若构成回路，则舍弃，不能加入TE中。
4. 再选取最小边，重复执行第三步，直到TE中包含n-1条边为止，最后的T即为最小生成树。

这个算法的难点在于，在选取权最小的边后，如何判断该边有没有使T构成回路。这里推荐一种方法：

将n个顶点划分为n个集合，就是每个集合只有一个顶点，表明他们之间互不相同，各自为无回路的连通分支。当选取一条边后：

• 若这条边俩个顶点不属于同一集合，则表明了改边连通了俩个不同的连通分支，又因为每个连通分支都是无回路的，所以连通俩个连通分支后，也无法形成回路，所以该边保留，作为T的一条边。然后把这条边的俩个顶点所在集合合并为一个集合，构成一个新的无回路的连通分支。
• 若这条边俩个顶点不属于同一集合，则舍弃，因为同一个集合中的顶点是连通无回路的，若加入一条俩个顶点都属于本集合的边，必会形成回路。

最小生成树的可以通过Kruskal(克鲁斯卡尔)算法或Prim(普里姆)算法求出。

Prim算法基本介绍：

Prim算法又称为"加点法"，每次找出距离(此处的距离指的是距离最小生成树的距离，若此处无法理解，可直接跳过，看完下面例子就能理解)最小的边对应的点。算法逐渐从某一个顶点s开始，逐渐将n个点纳入最小生成树中。

Prim算法基本步骤：

第一步：设图中所有顶点的集合为V，u代表已经加入最小生成树的顶点的集合，v代表未加入最小生成树的顶点的集合，最由于从某点s开始，因此u={s}，v={V-u}

第二步：在两个集合u,v中选择一条代价最小的边，将在v中连接这条边的那个顶点x加入到最小生成树顶点集合u中，并且更新与x相连的所有邻接点

第三步：重复上述步骤，直到最小生成树顶点集合u中有n个顶点为止

 Prim算法步骤演示，以下图为例：min数组代表，每个顶点到最小生成树的距离，以0为起点，0到最小生成树的距离就为0

  1.初始化：u={0}，v={1,2,3,4,5,6}，0加入到最小生成树集合u中，将0设置为蓝点，紧接着更新与0连接的邻接点1和3，此时0是最小生成树的一部分，1到最小生成树的距离为8，3到最小生成树的距离为5。

  2.此时u={0}，v={1,2,3,4,5,6}，在u,v两个集合中选择一条代价最小的边，下图为例就是5，根据算法步骤，将在v中连接这条边的顶点3加入到最小生成树集合u中，此时u={0,3}，v={1,2,4,5,6}。然后更新与3连接的所有顶点到最小生成树的距离，1到最小生成树的距离更新为3，5到最小生成树的距离更新为7，6到最小生成树的距离更新为15

  3.此时u={0,3}，v={1,2,4,5,6}，在u,v两个集合中选择一条代价最小的边，下图为例就是3，根据算法步骤，将在v中连接这条边的顶点1加入到最小生成树集合u中，此时u={0,3,1}，v={2,4,5,6}。然后更新与1连接的所有顶点到最小生成树的距离，2到最小生成树的距离更新为12，4到最小生成树的距离更新为10

  4.此时u={0,3,1}，v={2,4,5,6}，在u,v两个集合中选择一条代价最小的边，下图为例就是7，根据算法步骤，将在v中连接这条边的顶点5加入到最小生成树集合u中，此时u={0,3,1,5}，v={2,4,6}。然后更新与5连接的所有顶点到最小生成树的距离，2到最小生成树的距离更新为2，4到最小生成树的距离更新为9

  5.此时u={0,3,1,5}，v={2,4,6}，在u,v两个集合中选择一条代价最小的边，下图为例就是2，根据算法步骤，将在v中连接这条边的顶点2加入到最小生成树集合u中，此时u={0,3,1,5,2}，v={4,6}。然后更新与2连接的所有顶点到最小生成树的距离，4到最小生成树的距离更新为6

  6.此时u={0,3,1,5,2}，v={4,6}，在u,v两个集合中选择一条代价最小的边，下图为例就是6，根据算法步骤，将在v中连接这条边的顶点4加入到最小生成树集合u中，此时u={0,3,1,5,2,4}，v={6}。然后更新与4连接的所有顶点到最小生成树的距离，发现4没有邻接点可以更新

  6.此时u={0,3,1,5,2,4}，v={6}，在u,v两个集合中选择一条代价最小的边，下图为例就是15，根据算法步骤，将在v中连接这条边的顶点6加入到最小生成树集合u中，此时u={0,3,1,5,2,4,6}，v={}。然后更新与6连接的所有顶点到最小生成树的距离，发现6没有邻接点可以更新

Prim算法执行完成后得到的最小生成树为：

最终，将min中的值进行求和，结果为0+3+2+5+6+7+15=38，因此MST的值为38。有兴趣的朋友可以以此题为例，利用Kruskal算法求出最小生成树😊😊。

你若盛开,蝴蝶自来;你若精彩,天自安排！算法学习贵在坚持，各位小伙伴们要坚持噢！如果对于以上博文有任何疑问，可以联系本人。wechat：Q1313135😄