最小生成树原理

图的最小生成树

在图论中，如果一个连通的子图包含图的所有结点，那么这个子图称为图的生成树。生成树包含所有结点的连通子图中的极小连通图。图的生成树不唯一。从任意一个顶点开始遍历(dfs,bfs都可)，都会得到一个不同的生成树。
在带权图的所有生成树中，权值之和最小的称为最小生成树。
最小生成树的几个性质：

最小生成树是一个连通图
最小生成树是一棵无环树，因此有n-1条边，树上任意两节点之间路径唯一。

常用的生成树算法有DFS生成树、BFS生成树、Prim 最小生成树和Kruskal最小生成树算法
求一个图的最小生成树的方法有两种：Kruskal算法和Prim算法。

Kruskal算法

Krusakl算法求最小生成树，是借助于并查集完成的一个求最小生成树简单易实现的算法。
首先要知道几个性质：

一个连通块可以看成一个集合，这就是引入并查集的地方
两个连通块之间的所有边中，权值最小的那条边一定参与构成最小生成树。

在一个带权的无向连通图中，先对所有的边的权值进行从小到大排序，然后，遍历这些边，如果这条边的两个端点在同一个集合内，即在同一个连通块中，那么这条边就不在最小生成树中；否则，这条边在最小生成树中，然后将这条边的两个点所在的连通块合并，即合并两个集合即可；当已选的边的数目为总结点的数目-1(n-1)时，说明最小生成树已经构成。前两个操作恰好对应于并查集的查询两个元素是否在同一集合内和合并两个集合，所以用并查集刚好可以解决这个问题。
最小生成树模板 洛谷P3366

#include <algorithm>
#include <iostream>
using namespace std;
const int maxn = 2e5+5;
typedef struct edge{
    int u,v,w;
}Edge;
int n,m;
int fa[5050];
Edge e[maxn];
inline bool cmp(Edge a,Edge b){
    return a.w < b.w;
}
inline int find(int x){
    while (x!=fa[x])    x = fa[x] = fa[fa[x]];
    return x;
}
int main(){
    std::ios::sync_with_stdio(false);
    int ans,x,y,now;
    cin >> n >> m;
    for (int i=1;i<=m;i++)
        cin >> e[i].u >> e[i].v >> e[i].w;
    sort (e+1,e+m+1,cmp);          //按权值排序
    ans = now = 0;
    for (int i=1;i<=n;i++)  fa[i] = i;
    for (int i=1;i<=m;i++){
        x=find(e[i].u), y=find(e[i].v);
        if (x==y)   continue;          //两个结点属于同一连通块时
        ans += e[i].w;
        fa[x] = y;
        if (++now==n-1) break;
    }
    cout << ans;
    return 0;
}