最小生成树
最小生成树也是一种常见的有权无向图问题，为了解决此问题，引出了本章的两个算法。
本章将包括：
目录一.基本概念
1.什么是最小生成树？
在一幅有权无向图中，把联通所有点且不含回路的一个子图称为一棵生成树，其中边权最小的生成树称为最小生成树(简称 \(MST\) )。
2. \(MST\) 算法的思路
\(MST\) 的计算有一个性质，即为最短的边一定在 \(MST\) 上，由是可以得出通过贪心来构建 \(MST\) ，因为为其满足“全局最优解由局部最优解组成”的最优性定理。
二. \(kruskal\) 算法
1.算法思路
\(kruskal\) 算法的思想为对每条边进行贪心，由于最短边一定在 \(MST\) 上这个原理，我们从最短的边开始，将其加入集合 \(T\) 中，在剩余的边中，找最短的边重复操作，直至 \(T\) 包含 \(n-1\) 条边或所有点都在集合 \(T\) 中。
由于 \(MST\) 不存在环，所以我们在进行操作时，要维护一个并查集结构，来保证其无环。
2.代码详解
由于其只用到了边的关系，我们只需维护一个简单的边集数组即可。
struct node{
int u,v,w; //边集数组，u为起点，v为终点，w为边权
}e[maxn];
bool cmp(node a,node b){
return a.w<b.w; //排序用的cmp函数，对边进行排序，找最小边
}
int fa[maxn];
int find(int x){ //并查集的查询操作
if(x!=fa[x])
fa[x]=find(fa[x]); //路径压缩优化
return fa[x];
}
int kruskal(){
sort(e+1,e+m+1,cmp);
for(int i=1;i<=n;i++) fa[i]=i; //并查集初始化
int ans=0;
for(int i=1;i<=m;i++){
int u=e[i].u,v=e[i].v,w=e[i].w;
if(find(u)==find(v)) continue; //若已是联通
else{
ans+=w; //统计答案
fa[find(u)]=find(v); //联通
}
}
return ans;
}
3.算法总结
\(kruskal\) 算法编码较简单，无需邻接矩阵或是邻接表等复杂的存图方式，只需一个边集数组即可，具体处理方面也无需复杂的计算，只需进行一遍“排序+并查集”即可。
三. \(Prim\) 算法
1.算法思想
不同于 \(kruskal\) 算法对边进行贪心， \(Prim\) 算法注重对点进行贪心。以点为进一步贪心的线索，由生成树的定义可知，一棵生成树一定包含此图中的所有点。所以，我们可以以任意点为起点，进行 \(MST\) 的计算。
对于每个点来说，由于 \(MST\) 的性质，我们选择其出度权值最小的那一条，然后判断此边链接的点是否已在 \(MST\) 即可。是不是有点熟悉，是得，这与 \(Dijkstra\) 算法的贪心思路一致，不过是略微修改。
2.代码详解
int prim(){
int s=1; //若以1为起点
for(int i=1;i<=maxn;i++) done[i]=false; //初始化，done[i]表示点i是否在队列中
priority_queue<node> q; //优先队列，存边权的长度
q.push(node(s,0));
int ans=0;
while(!q.empty()){
node u=q.top();
q.pop();
if(done[q.id]) continue; //表示以在MST中，跳过
done[q.id]=true; //标记存在
ans+=q.w;
for(int i=0;i<g[u.id].size();i++){ //枚举全部邻居
edge y=g[u.id][i];
if(done[y.to]) continue; //若邻居已入队，跳过
q.push(node(y.to,y.w)); //其邻居入队
}
}
return ans;
}
3.算法总结
由代码可看出， \(Prim\) 算法与 \(Dijkstra\) 算法的代码十分相近，只是不用维护到起点的距离 \(dis\) 若 \(Prim\) 算法使用优先队列，则总复杂度为 \(O(mlog_2n)\) ;
四.总结
最小生成树是图论算法中较为重要的一种问题，当然其算法较为简单，但应充分理解其思想。
标签：int,MST,最小,生成,算法,贪心 From： https://www.cnblogs.com/adsd45666/p/18263463