（先更新到这，后面有时间再补，嘤嘤嘤）
今天给大家简单的讲一下最小生成树的问题吧！（ps:本人目前还比较菜，所以最小生成树最后的结果只能输出最小的权值，不能打印最小生成树的路径）
本Tianc在刚学的时候，经常把最小生成树问题和最锻炼吧问题弄混淆，最后事实证明这两个问题是存在着相似点的。
所以还是可以参照我上一篇的博客 https://www.cnblogs.com/laysfq/p/9808088.html（此处插个"广告"）
最小生成树的实质问题还是求最短的路径（是吧？肯定是的！）
kruskal算法（用边进行更新）
我的kruskal算法中用到了并查集，这样的话比较好找父结点，它的具体过程是这样的：
先将他们的权值进行映射排序，然后从最小的权值里面的取出结点数，放到树里面作为根结点，然后用并查集进行连接，每连接一个点，
把这条边所对应的权值加进去，查询下一个结点。不断的更新，直到把所有的点全部放到树里面。
下面是代码:
#include<iostream> #include<algorithm> using namespace std; const int maxn = 10000000; int n,m; int u[maxn], v[maxn], w[maxn], pre[maxn], r[maxn]; int fun(int i, int j) { return w[i] < w[j]; } int find(int x) { return pre[x] == x ? x : pre[x] = find(pre[x]); } int kruskal() { int ans = 0; for (int i = 0; i < n; ++i) pre[i] = i; for (int i = 0; i < m; ++i) r[i] = i; sort(r, r + m, fun); for (int i = 0; i < m; ++i) { int temp = r[i]; int x = find(u[temp]); int y = find(v[temp]); if (x != y) { pre[x] = y; ans += w[temp]; } } return ans; } int main() { while (cin >> n>> m) { for (int i = 0; i < m; ++i) { cin >> u[i] >> v[i] >> w[i]; } cout << kruskal() << endl; } }
呃呃呃，上面是程序运行的结果，第一行的5和7表示的是结点数和边的数目，下面会输入7行，例如“1 2 5”，表示的是1和2之间的权值是5。
最后输出最小生成树中权值总和。
Prim算法（用点进行更新）
这个是用点进行更新的，先将权值最小的边找出来，然后把最小的边对应的两个结点放进图中，然后利用这两个点向外不断的扩展，依据就是找出和这两个点相连且权值最小的且不在图里面的点。直到最后将所有的点访问完，构成一棵最小生成树。
附上代码：
#include<iostream> using namespace std; const int INF = 0x3f3f3f3f; const int MAXN = 110; bool vis[MAXN]; int lowc[MAXN]; int Prim(int cost[][MAXN], int n)//点是1-n { int ans = 0; memset(vis, false, sizeof(vis)); vis[1] = true; for (int i = 2; i<=n; i++)lowc[i] = cost[1][i]; for (int i = 2; i<=n; i++) { int minc = INF; int p = -1; for (int j = 1; j<=n; j++) if (!vis[j] && minc>lowc[j]) { minc = lowc[j]; p = j; } if (minc == INF)return -1;//原图不连通 ans += minc; vis[p] = true; for (int j = 1; j<=n; j++) if (!vis[j] && lowc[j]>cost[p][j]) lowc[j] = cost[p][j]; } return ans; } int main() { int n, m; int a, b, c; int cost[MAXN][MAXN]; while (cin >> n >> m) { for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { if (i == j) cost[i][j] = 0; else cost[i][j] = INF; } } for (int i = 0; i < m; ++i) { cin >> a >> b >> c; cost[a][b] = cost[b][a] = c; } cout << Prim(cost, n)<<endl; } }