最小生成树

Kruskal

将所有的边从小到大排序,然后依次加入图中,中间用并查集判断是否在一个连通分量中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Edge{
int u,v,w;
bool operator<(const Edge& rhs) const {
return w<rhs.w;
}
} e[maxm];
int p[maxn];

find(int x){ //并查集
return p[x]?p[x]=find(p[x]):x;
}

int kruskal(){
int ans=0;
memset(p,0,sizeof p);
sort(e,e+m);
for(int i=0;i<m;++i){
int u=find(e[i].u),v=find(e[i].v);
if(u!=v){ //不在同一连通分量
p[u]=v;
ans+=e[i].w;
}
}
return ans;
}

Prim

增量最小生成树

从含n个点的空图开始,依此加入m条带权边,没加入一条边,输出当前图中最小生成树的权值

加入一条边后,构成了一个环,然后删除这个环上权值最大的边(dfs)

复杂度 $O(nm)$

最小瓶颈生成树

使最大的边权尽量小

原图的最小生成树即最小瓶颈生成树

最小瓶颈路

给定加权无向图的两个节点u,v,求从u到v的一条路径,使得路径上的最大边权尽量小

最小生成树上的唯一路径即所求

次小生成树

所有生成数中权值第二小的

枚举不在最小生成树上的边,然后分别添加进最小生成树,求一个最小的答案

最小树形图