这个是图论的倒数第二章。我会着重讲解最小生成树和拓扑排序两个算法。如果哪些地方我写错的，或者没写清楚的，可以评论区吐槽~
先看一道洛谷上面的题目。
题目大意就是给n个点，m对长度，求一个最小生成树。
什么叫做最小生成树？我们之前讲树的时候提到过，树一共有n-1条边，然后每条边都是一个割边—删去这条边，图就不连通。最小生成树就像上题所说，找出一部分边，保证整个图是联通的，并且所有边的长度最小。
我们再仔细思考一下，要保证边的总长度最小，是不是必须要是一棵树？可以说是的，如果这一张图，某条边不是割边（删除后依旧是连通图），那么我们删去他，也能满足条件，并且边的长度更小。（这里的前提是所有边的权值是正数）同时，如果所有的边都是割边，那显然这应该是一棵树。
好的。我们该如何找到这棵树？
很明显，我们能想到一个贪心的算法。实际上我们的目标就是找到n-1条长度最小的边，然后要保证这些边能使得所有点连通。
我们来试一试。下面有一张图。
这个算法叫Kruskal算法。时间复杂度O(ElgV)
我重新描述一下整个算法过程。
1. 先将所有的边按照长度从小到8大排序。
2. 从小到大遍历。如果这条边没必要连接（连接会导致成环），就舍弃这条边；否则我们就将这条边连起来。
3. 最后形成的图就是最小生成树。
并查集可以让我们知道两个区块是否联通，我们只要判断这条边连接的两个点是否是联通的就行（即根节点是否相同）
洛谷标程如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll fa[100005];
struct node{
ll x,y,c;
}a[100005]; //代表每条边连接x和y长度为c
ll n,m;
ll find_fa(ll x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;} //并查集核心算法
bool cmp(node x,node y){return x.c<y.c;} //边排序
ll read(){ //快读
char c=getchar();ll x=0;
while(!isdigit(c)) c=getchar();
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x;
}
int main(){
n=read();m=read();
ll ans=0;
for(ll i=1;i<=m;i++){a[i].x=read();a[i].y=read();a[i].c=read();}
for(ll i=0;i<n;i++) fa[i]=i;
sort(a+1,a+1+m,cmp);
for(ll i=1;i<=m;i++){
ll fx=find_fa(a[i].x),fy=find_fa(a[i].y);
if(fx!=fy){
ans+=a[i].c;
fa[fx]=fy;
}
}
cout<<ans<<endl;
return 0;
}
存稿用完啦！大家有问题可以留言～
