给一张n个点的图，从中选 n-1条边，使得所选边权和最小的情况下生成一个树。
解法核心：贪心
1、核心思路： 点集拓展
2、核心操作：贪心（优先队列实现） + 判环（集合/标记 实现）
3、算法流程：
step1. 随机选取一个点不在集合内的点，并将该点连接的所有边加入优先队列，
step2. 选取优先队列的top（即集合当前所连接所有边中的最短边），将该边作为树的其中一个边，
step3. 将所连向的to_pos加入集合，如果该点已经在集合，则换下一条边，进行前述操作。
step4. 重复上述操作，直到所有点全部加入集合
注：推荐使用邻接矩阵。
4、复杂度分析：
O( N + logM) ⇒ 适用于密集图（边较多时）
5、 代码模板：
struct ss{
int to,nex,va;
bool operator >const (ss b){return va<b.va;}
}edge[N];int head[N],ecnt;
priority_queue<ss> Q;
int prim(){
vis[1]=true;int count=1,ans=0;
for(int i=head[1];i;i=edge[i].nex) Q.push(edge[i]);
while(count<n && !Q.empty()){
int to=Q.top().to;Q.pop();
if(vis[to]) continue;
count++;ans+=Q.top().va; vis[to]=true;
for(int i=head[to];i;i=edge[i].nex)
if(!vis[edge[i].to]) Q.push(edge[i]);
}if(count<n) return -1;
return ans;
}
1、核心思路： 选边法
2、核心操作：贪心（一次排序实现） + 判环（并查集实现）
3、算法流程：
step1. 将所有边排序
step2. 每次都选取最短的边，将该边作为树的边，
如果该边所连向的两个点 已经在同一并查集，则弃之不用
否则该边合法，选用该边，更新并查集
step4. 重复前述操作，直至n-1条边被选用，或直至所有边被遍历一遍
4、复杂度分析：
算法复杂度： O(m logm) ⇒ 适用于稀疏图（边较少时)
5、 代码模板：
struct ss{
int x,y,va;
}edge[N];int f[N];
bool cmp(ss a,ss b){return a.va<b.va;}
int fa(int x){
if(f[x]==x) return x;
else return f[x]=fa(f[x]);
}
int krustra(){
sort(edge+1,edge+m+1,cmp);int ans=0,count=0;
for(i=1;im;i++){
int x=edge[i].x,y=edge[i].y;
if(fa(x)==fa(y)) continue;
ans+=edge[i].va;
f[x]=fa(y);
count++;if(count==n-1) break;
}return ans;
}
注： prim算法如果要做非连通图的最小生成森林树，则需外面加一个循环，将所有点都视为初始放入节点。
ps.补一些基础模板，以便自己使用
Original: https://blog.csdn.net/l961983207/article/details/127821915
Author: GoesM
Title: 【模板】MST最小生成树（Prim算法、Krustra算法）
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/659270/
转载文章受原作者版权保护。转载请注明原作者出处！