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