几分钟搞明白生成树和最小生成树的定义

柔光的暖阳◎ 2022-06-05 02:15 266阅读 0赞

注意文字意思：不管是生成树还是最小生成树一定还是输，千万别和图混淆了。

下面来说生成树：我们这棵树是针对图来说的，如果你们已经知道极小连通子图就非常简单了，  
极小连通子图什么意思呢，就是我们把图中的全部节点连接起来，假如n个节点那么，边是n - 1条。

注意形成的一定是一棵树才是生成树。

好了回到正题：  
那么我们的生成树怎么在图的基础上生成的呢？  
我们学了图应该知道有2种遍历方法：1深度优先遍历 2广度优先遍历  
深度优先遍历（DFS）是什么意思呢：假定一个起点比如下图所示：  
![这里写图片描述][SouthEast]

假如我知道0的地址，我们使用深度优先遍历算法遍历当前的图：  
分析：深度字面意思一定要搞定这个意思就是说我们根据当前节点访问当前节点的一个孩子，然后在访问孩子节点的一个孩子节点，一直递归下去。直到全部节点访问完毕就停止访问，否则我们就退到上个节点从另一个孩子节点开始使用相同方式访问孩子节点。  
![这里写图片描述][SouthEast 1]

分析：由深度优先遍历算法得到的生成树如上图；

我们从起点0开始，找到0的第一个邻节点2， 因此0->2->3->4->1->5.  
这个序列是确定的吗，在这个图是确定的，先0我们在找邻节点我们假如在逆时针方位开始0开始找到第一个邻节点也就是2并且都标为访问过然后就找到2的邻节点3 在就是4在就是1，这个时候是不是有4个方位，但是只有5没有访问因此就是5 这个时候全部访问完毕。

第二个办法就是广度优先算法生成树：

![这里写图片描述][SouthEast 2]

分析：我们来看看这个生成树是怎么形成的， 我们还是0开始，标志为被访问，  
然后由于是广度优先访问全部的邻节点在访问孩子的全部邻节点 0->2 1 5 3 4

现在引入我们的最小生成树的定义：既然是最小在是生成树的基础上，在加上假如是带权值，那么生成树的很多种当中必有一个生成树权值和是最小，那么最小那棵树就是最小生成树。

那么权值是什么意思，比如0节点和2节点之间我们可以看成是一个城市到一个城市的车费或者路程。  
那么最小就是走遍全部城市的车费或者路程最小。

[SouthEast]: /images/20220605/9f97fabf9925473ab6cf9da1b597863f.png
[SouthEast 1]: /images/20220605/52dcc8fa8d964626a0d5fb0f3a6c91fc.png
[SouthEast 2]: /images/20220605/e90834d6ffe741cba689193ecc492c38.png