最小生成树

Catalogue

1. 1. 什么是最小生成树
   1. 1.1. 前置要求
2. 2. 应用场景举例
3. 3. 求证思路

什么是最小生成树

在一个有权图中，所有的边连接为一个图，那么用最少的边将所有节点连接起来且该连接和最小，可以称为最小生成树

1. 如上图: 图中==红色边==连接起来的就是最小树，既然最小，那么图就是有权的（有可比较的数值）
2. 最小生成树 一定有v-1条边 v是顶点，也就是每个点只有一条连接

   前置要求

• 带权无向图 (每个节点具有可比较的值)
• 针对连通图

应用场景举例

1. 铁路线路构建

每个城市之间其实不需要都建立铁轨，只要保证所有的城市之间能够连通即可

如上图:所有城市组成了一个图，而所有边是城市的连接.
那么只有红色边是需要建立铁轨的，且保证了所有城市都有连通线路

2. 电线布局

依然如此，使用最短的路径来连接所有节点

求证思路

假入我们有如下组成的图结构:

总共有a,b,c,d,e,f6个节点，且存在10条边，每条边上的数字代表了该路径权值. 拿上面铁轨来说就是每个城市之间的距离。现在需要求出最小生成树，也就是去掉无关的边

1. 从a开始访问，将a的所有边加入最小堆中，且标记a为已访问`
   

   从a出发有3条边 a-b a-e a-c
   那么可以看到a-b的权值为1 最小，且b没有访问过那么a-b就一定是
   最小生成树的一条边，进行标记并去除最小堆

2. 将b的所有连接边加入最小堆,并取出最小权值的边
   

   可以发现b-f在最小堆中权值最小，且f点未被访问过.
   那么b-f绝对是最小生成树中的一条边，对f进行标记并移除最小堆

3. 将f对应的边加入最小堆，并取出最小权值的边
   

   f-c 权值为2，目前为堆中最小，且c未被访问过，则f-c为生成树的一条边
   进行标记，剔除最小堆

4. 没有新加入边则，继续在堆中找出最小边
   

   发现有三个节点的权值相同，但有一点不同
   b-c a-c 两个边的点都被标记过了，所以需要剔除
   最后只剩下b-e 最小，则进行标记并剔除最小堆

5. 加入e关联的边，继续找出堆中最小边
   

   a-e 已经访问过了，需要剔除
   e-d 最小，且d未访问过，则一定是最小生成树的边，进行标记、剔除

这样基本就全部访问完了，接下来就是剔除无关的边，最后得出如下最小生成树