kruskal()
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int M = 1e5 + 10; 4 const int N = 1e5 + 10; 5 int fa[N]; 6 int get(int x) { 7 return fa[x]==x? x: fa[x]=get(fa[x]); 8 } 9 void merge(int x, int y) { 10 fa[get(x)] = get(y); 11 } 12 struct rec { 13 int x, y, z; 14 bool friend operator<(const rec& a, const rec& b) { 15 return a.z < b.z;//边权较小的排在前面 16 } 17 }e[M]; 18 int n;//点的数量 19 int m;//边的数量 20 int ans; 21 bool kruskal() { 22 for (int i=1; i<=n; ++i) fa[i] = i;//起初每个点各自构成一个集合 23 sort(e+1, e+1+ m);//按照边权排序 24 int cnt = 0; 25 ans = 0; 26 for (int i=1; i<=m; ++i) { 27 int fx=get(e[i].x), fy=get(e[i].y);//查询 x,y分别属于哪个集合 28 if (fx == fy)continue;//如果已经在同一个集合就继续扫下一条边 29 merge(fx, fy);//将 x,y 所在的两个集合合并 30 cnt++;//已经找到的边数加 1 31 ans += e[i].z;//答案累加这条边的权值 32 } 33 return cnt == n-1;//如果找的边数恰好有n-1条边，则存在最小生成树。否则不存在 34 }
prim()
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int M = 1e5 + 10; 4 const int N = 1e3 + 10; 5 const int inf = 0x3f3f3f3f; 6 int mp[N][N];//邻接矩阵存图 7 int d[N]; 8 bool vis[N];//标记数组 9 int n;//点的数量 10 int m;//边的数量 11 int ans; 12 bool prim() { 13 memset(vis, 0, sizeof vis);//标记数组初始化 14 memset(d, inf, sizeof d);//将d 数组初值都设为无穷大 15 d[1] = 0;//先确定1号点属于最小生成树 16 for (int i=1; i<n; ++i) {//执行 n-1 次，找剩余的 n-1 个点 17 int x = 0; 18 for (int j=1; j<=n; ++j) 19 if (!vis[j] && (x==0 || d[j]<d[x])) 20 x = j;//找出未被标记的且 d 值最小的一个点 21 vis[x] = 1;//将这个点标记，表示该点已被收录进最小生成树的集合 22 for (int y=1; y<=n; ++y) 23 if (!vis[y]) 24 d[y] = min(d[y], mp[x][y]);//扫描该点的所有出边，更新令一端点的 d 值 25 } 26 ans = 0; 27 for (int i = 2; i <= n; i++) { 28 if (d[i] == inf) return false;//如果有一个点的 d 值还是无穷大，说明该点被孤立，原图不存在最小生成树 29 ans += d[i];//累加答案 30 } 31 return true; 32 }