type
status
date
slug
summary
tags
category
icon
password
Email
文章首发于：My Blog 欢迎大佬们前来逛逛
概念
最小生成树的定义 在一张带权无向图中，最小生成树是一棵生成树，它的边权值之和最小。
生成树是一颗包含原图中所有顶点的树，它的边集合是原图的一个子集，且任意两个顶点之间都有且仅有一条简单路径。
最小生成树的算法目前，最常用的两种最小生成树算法是Kruskal算法和Prim算法。
Kruskal算法
Kruskal算法 Kruskal算法的主要思想是按照边权值从小到大依次选择边，如果这条边的两个端点不在同一个连通块中，就把这条边加入到最小生成树的边集合中。 具体实现步骤：
（1）将所有边按照边权值从小到大排序。
（2）从小到大依次选择每一条边，如果这条边的两个端点不在同一个连通块中，就把这条边加入到最小生成树的边集合中，并合并这两个连通块。
（3）重复步骤（2），直到最小生成树中有n-1条边为止。 Kruskal算法的时间复杂度为O(mlogm)，其中m为图中的边数。
Kruskal算法存储每一条边（不是双向边），并且还需要对于每个节点的辅助数组，因此对于边和点的数据类型的范围应该这样定义：
Kruskal算法适合于稀疏图
证明：如果某个连通图属于最小生成树，那么所有从外部连接到该连通图的边中的一条最短的边必然属于最小生成树。所以不难发现，当最小生成树被拆分成彼此独立的若干个连通分量的时候，所有能够连接任意两个连通分量的边中的一条最短边必然属于最小生成树
Prim算法
Prim算法 Prim算法的主要思想是从任意一个顶点开始，每次选择一个与当前连通块相邻的权值最小的边，并将其加入到最小生成树的边集合中，直到所有顶点都被加入到最小生成树中。 具体实现步骤：
（1）随机选择一个顶点作为起始点。
（2）将与起始点相邻的边按照边权从小到大排序，并选择权值最小的边加入到最小生成树的边集合中。
（3）将新加入的点加入到连通块中，并将与它相邻的边按照边权从小到大排序。
（4）重复步骤（2）和（3），直到所有顶点都被加入到最小生成树中。
Prim算法的时间复杂度为O(n^2)，其中n为图中的顶点数。但是，如果使用堆优化的Prim算法，时间复杂度可以优化到O(mlogn)。
Prim算法存储每一条边，而且是双向边，使用链式前向星存图的边集合和点集合的数据范围应该如下定义：
Prim算法适合于稠密图
最小生成树的应用 最小生成树广泛应用于网络设计、电路设计、城市规划等领域。
例如，在网络设计中，最小生成树可以用来寻找最短路径，从而优化网络性能；
在城市规划中，最小生成树可以用于道路和管道的布局，从而降低建设成本。
3728. 城市通电
题目要求：由n个城市，每两个城市之间可以选择连电线或者建电站，规定要使得所有的城市都必须通电。城市通电的要求是这个城市建有电站或者与其他建有电站的城市连接。并且规定每个城市建电站和建电线费用，求得最小的使得全部城市通电的总费用。
我们很容易看出这是一个最小生成树的问题，貌似只需要求出任意两点之间的边的边权，我们直接用Prim或者Kruskal不就结束了吗。
但是我们这样直接做是基于图中只存在边权，即只有建电线；但是这道题还规定了我们可以不用建电线，还可以在自己所在的位置建电站。
如果三个点信息是这样的：
电站代价：1 1 2；电线代价：5 5 8
则我们直接求最小生成树一定是错误的，这样的话答案为 13 ，但是很明显直接在每个点上建电站不就好了，这样的话答案为 4.
如果解决这种问题呢？ 使用超级源点即可。
我们规定一个不存在的点连接连接每一个城市，并且规定所连的边的权值为每个对应的城市建电站的代价。
则我们用图来表示这样的关系：
我们既然求绿色的最小生成树不可行，则建立虚拟源点后，直接求对于整个的图的最小生成树，这样就解决了我们刚才的问题。
即如果刚才每个城市都建立电站，则对与整个图来说，最小生成树就是每个点的建电站的代价和（因为超级源点到每个点的边权规定为建电站的代价）
注意：对于原图中每两个点之间的权值需要我们单独求出。
然后直接对这整个图进行一次最小生成树即可
注意Prim算法的建边所需要的空间
Prim
Kruskal
- 作者:Yuleo
- 链接:https://www.helloylh.com/article/zuixiaoshu
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。