最小生成树定义：
构造连通网的最小代价生成树称为最小生成树(Minimum Cost Spanning Tree)。即有n个城市，如何修最短的路将所有的城市连接起来。
构造最小生成树主要有两种算法一种是普里姆（Prim）算法，一种是克鲁斯卡尔（Kruskal）算法。
Prim在稠密图中比Kruskal优，在稀疏图中比Kruskal劣。Prim是以更新过的节点的连边找最小值，Kruskal是直接将边排序。
1.普里姆算法
先选择图中任意一个顶点作为起始点，之后选择连接这个顶点最短的一条边，将其与另一个顶点连接上。将这两个已经连接的点看成一个入度更多的一个大顶点，继承两个
顶点的所有边，之后再找出这个大顶点最短的一条边，将其与另一个顶点连接上。以此类推将这已经连接的三个点继续看成一个大顶点，继续连接，直到图中所有的顶点已经
连接上，这样构成的图便是一个最小生成树。
普里姆算法主要基于一个判断：对于任意一个顶点v，连接到该顶点的所有边中的一条最短边(v, vj)必然属于最小生成树。
int n, m;
int dis[5005], vis[5005];//dis记录当前到所有点的最小值，vis判断当前点是否走过
struct edge {
int to, weight;//储存边的结构体，to终点，weight权值
};
vector<edge>edg[5005];//储存边的邻接表
class Solution {
public:
static int prim() {
int tot = 0, cur = 0, answer = 0;//tot已经连接的点的数量，cur当前连接的点，answer答案
for (int i = 1; i <= n; i++) {
vis[i] = 0; dis[i] = 0x7fffffff;//初始化数组
}
dis[1] = 0;//选择1号顶点为初始点
while (++tot <= n) {
int minn = 0x7fffffff;
for (int i = 1; i <= n; i++) {//寻找最短边
if (!vis[i] && dis[i] < minn) {
minn = dis[i];
cur = i;
}
}
answer += dis[cur];//更新答案
vis[cur] = 1;//标记当前点已经走过
for (int i = 0; i < edg[cur].size(); i++) {//用当前选出的点更新距离数组dis
dis[edg[cur][i].to] = min(dis[edg[cur][i].to], edg[cur][i].weight);
}
}
return answer;
}
};
2.克鲁斯卡尔算法
克鲁斯卡尔算法相比普里姆算法更好理解，第一步将图中所有的边放到一个数组里面，第二部将数组中的边按照权值从小到大排序 ，第三部从小到大选择n-1条边加入生成树中，同时利用
并查集来保证不会形成环。这样构成的生成树就是最小生成树。
bool cmp(edge x, edge y) {
return x.weight < y.weight;
}
class Solution
{
static int find_father(int x) {
return fa[x] == x ? x : fa[x] = find_father(fa[x]);//寻找父节点
}
public:
static void Kruskal() {
int n, m, ans = 0, tot = 0;
cin >> n >> m;
for (int i = 1; i <= n; i++)fa[i] = i;
for (int i = 1; i <= m; i++) {
int at, to, w;
cin >> at >> to >> w;
edge cur;
cur.at = at; cur.to = to; cur.weight = w;
edg.push_back(cur);
cur.at = to; cur.to = at;
edg.push_back(cur);//储存双边
}
sort(edg.begin(), edg.end(), cmp);
for (int i = 0; i < edg.size(); i++) {
int at = edg[i].at, to = edg[i].to;
if (find_father(at) != find_father(to)) {
fa[find_father(at)] = fa[to];
ans += edg[i].weight;
tot++;
}
if (tot == n - 1)break;//取了n-1个边便可以停止
}
if (tot < n - 1)cout << "orz";
else cout << ans;
}
};
标签：cur,weight,int,最小,生成,顶点,edg From： https://www.cnblogs.com/redintoncforever/p/17035836.html