求最小生成树的方法
目录
求最小生成树的方法
一、Kruskal（避圈法）
二、Prim算法
三、破圈法
一、Kruskal（避圈法）
1、把边按权值从大到小排序
2、依次补全边，如果形成回路就舍弃（避圈）
3、连接完所有点，判断边数是否为n-1
（生成树的特征是边数为n-1）
（kruskal在效率上更适用于稀疏图）
例：
边数排序：1，1，2，2，3，3，5
code：
#include
using namespace std;
typedef long long ll;
#define int ll
const int INF=0x3f3f3f3f;
const int N=6e5+10;
int n,m;
int ans = 0;
int cnt = 0;
int fa[N];
int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
struct edge{
int v;
int st;
int ed;
}e[N];
bool cmp(edge a,edge b){
return a.v } void klskr(){ for(int i=1;i<=m;i++) { int pa = find(e[i].st); int pb = find(e[i].ed); if(pa!=pb) //判回路 { ans+=e[i].v; fa[pa]=pb; cnt++; } } } void solve() { cin>>n>>m; for(int i=1;i<=n;i++) { fa[i]=i; } for(int i=1;i<=m;i++) //录边 { int a,b,c; cin>>a>>b>>c; e[i] = {c,a,b}; } sort(e+1,e+m+1,cmp); //边权从小到大排序 klskr(); if(cnt else cout< } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { solve(); } return 0; } 二、Prim算法 Prim和dij很像 1、每次找一个离集合距离最小的点 2、更新节点周围的节点的距离 3、每个点的距离之和就是最小生成树的权值和 （prim在效率上更适用于稠密图） code： #include using namespace std; typedef long long ll; #define int ll typedef pair //prim最小生成树稠密图 const int N = 510; int g[N][N];//存储图 int dt[N];//存储各个节点到生成树的距离 int st[N];//节点是否被加入到生成树中 int pre[N];//节点的前去节点 int n, m;//n 个节点，m 条边 void prim() { memset(dt,0x3f, sizeof(dt));//初始化距离数组为一个很大的数（10亿左右） int res= 0; dt[1] = 0;//从 1 号节点开始生成 for(int i = 0; i < n; i++)//每次循环选出一个点加入到生成树 { int t = -1; for(int j = 1; j <= n; j++)//每个节点一次判断 { if(!st[j] && (t == -1 || dt[j] < dt[t]))//如果没有在树中，且到树的距离最短，则选择该点 t = j; } //发现测试用例加强后，需要判断孤立点了 //如果孤立点，直返输出不能，然后退出 if(dt[t] == 0x3f3f3f3f) { cout << "impossible"; return; } st[t] = 1;// 选择该点 res += dt[t]; for(int i = 1; i <= n; i++)//更新生成树外的点到生成树的距离 { if(dt[i] > g[t][i] && !st[i])//从 t 到节点 i 的距离小于原来距离，则更新。 { dt[i] = g[t][i];//更新距离 pre[i] = t;//从 t 到 i 的距离更短，i 的前驱变为 t. } } } cout << res; } void getPath()//输出各个边 { for(int i = n; i > 1; i--)//n 个节点，所以有 n-1 条边。 { cout << i <<" " << pre[i] << " "<< endl;// i 是节点编号，pre[i] 是 i 节点的前驱节点。他们构成一条边。 } } void solve() { memset(g, 0x3f, sizeof(g));//各个点之间的距离初始化成很大的数 cin >> n >> m;//输入节点数和边数 while(m --) { int a, b, w; cin >> a >> b >> w;//输出边的两个顶点和权重 g[a][b] = g[b][a] = min(g[a][b],w);//存储权重 } prim();//求最下生成树 //getPath();//输出路径 return; } signed main() { ios::sync_with_stdio(0); cin.tie(0); int t=1; //cin >> t; while(t--) { solve(); } return 0; } 三、破圈法 设G= 破圈法是“见圈破圈”，即如果看到图中有一个圈，就将这个圈的最大权边去掉一条，直至图中再无一圈为止。