生成树

联通图$G$的生成树是包含$G$中所有顶点的极小连通子图

最小生成树

性质

  • 切割性质:在各边边权均不相同时,对于连接图$G$中两个非空点集的最短边$e$,$G$的任意$MST$一定包含$e$

  • 回路性质:在各边边权均不相同时,对于图$G$中的任意回路的最长边$e$,$G$的任意$MST$一定不包含$e$

Kruskal算法

对所有边按权值排序,最初每个点都是一个联通块

贪心地合并连接不同联通块的边,并查集维护

$O(m\log m+m\alpha(n))$

Prim算法

$Dijkstra$算法的变形,可以堆优化
可以处理负权边

增量最小生成树

在$MST$中新加入边$e=(u,v)$后,图中恰好包含一个环
根据回路性质,删掉$max(e,MST$中$(u,v))$即可

最小瓶颈生成树

最小化生成树中最大边权值
$MST$就是一棵最小瓶颈生成树

次小生成树

次小生成树可以由$MST$加一条边再删一条边得到

枚举不在$MST$中的$m-n+1$条边作为加入的新边,做增量最小生成树

最小树形图

给定一个有向带权图$G$和根节点$u$,找出一棵有向生成树,满足$u$的入度为$0$,其他结点入度均为$1$,且从$u$可以到达所有其他结点

朱刘算法

预处理:删除自环,判断根节点是否可以到达其他节点,不能的话无解

首先给所有非根结点选一条权最小的入边,并将这些入边的和累加入答案

如果没有环,现在所有的入边就构成了最小树形图

否则,将构成的环缩成一个点,注意n个点n条边只能构成一个最简单的环(因此不需要跑Tarjan强联通分量),找到上面的一个点,进行重标号即可

重复上述过程,直到没有环(显然只剩下一个点的时候也是没有环的)

但是这样是不对的……注意一个环中的某一个点x,再一次找x的最小入边的时候,根据流程要把x的最小入边的边权累加入答案,但是x原来的最小入边也累加入答案,显然这样是会重复的;那么不妨在缩点的时候让所有x的入边都减去当前x的最小入边,相当于去重

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
26
27
28
29
30
31
32
double dirtree(int rt)
{
double tmp=0;
while(1){
for(int i=1;i<=n;i++) in[i]=INF;
for(int i=1;i<=m;i++)
if(e[i].u!=e[i].v&&e[i].w<in[e[i].v])
pre[e[i].v]=e[i].u,in[e[i].v]=e[i].w;//定入边
in[rt]=0;
for(int i=1;i<=n;i++) if(in[i]==INF) return -1;//判断无解
int cnt=0;
for(int i=1;i<=n;i++) id[i]=vis[i]=0;
for(int j,i=1;i<=n;i++){
tmp+=in[i];
for(j=i;vis[j]!=i&&!id[j]&&j!=rt;j=pre[j]) vis[j]=i;//到根->环结束
//如果j已有标号或j为根的话就说明i之前的并不是正常的环
if(!id[j]&&j!=rt){
id[j]=++cnt;
for(int k=pre[j];k!=j;k=pre[k])//重编号
id[k]=cnt;
}
}
if(!cnt) return tmp;//已经无环
for(int i=1;i<=n;i++) if(!id[i]) id[i]=++cnt;//不在环中的单独点当作一个单点环处理
for(int i=1;i<=m;i++){
f=in[e[i].v];
e[i].u=id[e[i].u],e[i].v=id[e[i].v];//注意这里要用编号
if(e[i].u!=e[i].v) e[i].w-=f;
}
n=cnt,rt=id[rt];//!
}
}

$O(nm)$

最小斯坦纳树

使得指定集合中的点联通且权值和最小的生成树

$f[u][i]$表示以$u$为根,指定集合中的点状态为$i$的最小代价

1
2
3
4
5
6
7
8
9
10
11
12
memset(f,0x3f,sizeof(f));
int all=1<<k;//k:1~k为指定点集
for(int i=1;i<=k;i++) f[i][1<<(i-1)]=0;
for(int i=0;i<all;i++){
for(int u=1;u<=n;u++)
{
for(int s=i;s;s=(s-1)&i)
f[u][i]=min(f[u][i],f[u][s]+f[u][i^s]);//通过连通状态的子集进行转移
if(f[u][i]<INF) q.push(u),vis[u]=1;
}
spfa(i);//通过spfa松弛
}

$O(n3^k+cm2^k)$,其中$cm$为$spfa$的复杂度

生成树计数

Matrix-Tree 定理

对于无向图$G$,定义$G$的度数矩阵$D$满足

定义$G$的邻接矩阵$C$满足

定义$G$的基尔霍夫矩阵$Q=D-C$,则图$G$的不同生成树数量是$Q$的任意一个代数余子式

prufer序列

分享到: