生成树
前置知识:并查集,树与图
给定一张连通图,从图中选出数量最少的边,使得所有点仍然是连通的,那么选出的图一定是一棵树。
最小生成树
在生成树,边权之和最小的那一棵,称为最小生成树。
例如在市政规划时,管道要连接所有的节点,但是希望总长度最短等等
prim
把节点分为两个集合,一个是连通集合
先随便选一个点作为
选择连接
一共只有
cpp
bool vis[N];//是否在 S 集合
int dis[N];//S 集合到该点的最短距离
int sum=0;
vis[1]=1;dis[1]=0;
memset(dis,0x3f,sizeof(dis));
for(int k=1;k<=n;++k)
{
int pos=0;
for(int i=1;i<=n;++i)
{
if(!vis[i]&&dis[i]<dis[pos]) pos=i;//找到最近的那一条边
}
sum+=dis[pos];
vis[pos]=1;//将这个点加入集合
for(auto [t,v]:eg[pos]) dis[t]=min(dis[t],v);//将到 T 中的点的距离更新
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
这样复杂度是
正确性证明:
假设某一时刻连通集合是
当整张图连通时,将
kruskal
将边按长度从小到大排序,若这条边的两个端点还没有连通(用并查集判断),则将这条边选中。
cpp
typeedef array<int,3> edge;
vector<edge> eg(m+1);
for(int i=1;i<=m;++i)
{
cin>>e[i][0]>>a[i][1]>>a[i][2];
//e[i][0]和e[i][1]之间有一条权值为e[i][2]的边。
}
sort(e.begin()+1,e.end(),[&](edge a,edge b){
return a[2]<b[2];
});
vector<int> f(n+1);//并查集
for(int i=1;i<=n;++i) f[i]=i;
int sum=0;
for(int i=1;i<=n;++i)
{
int x=e[i][0],y=e[i][1];
x=find(x),y=find(y);
if(x==y) continue;
sum+=e[i][2];
f[x]=y;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
这样复杂度是
Boruvka
是一种多路增广的改进
开局有
因为每一轮每个连通块至少节点数量翻倍,所以一共只有
关键在于能否快速找到两个连通块之间的长度最小的边
例如:每个点有一个权值
开一个
每一轮的话要花