最小生成樹及應用

LINNO 2021-08-15 17:54:17 阅读数:693

本文一共[544]字,预计阅读时长:1分钟~
最小 小生 生成
title : 最小生成樹
date : 2021-7-30
tags : ACM,圖論

 

最小生成樹(MST)

什麼是最小生成樹問題?

我們給n個點m條邊,選出n-1條邊把所有點連起來(默認只有一塊),使得邊權之和最小,這就是最小生成樹(Minimum Spanning Tree)問題。

該問題有兩種比較常見的作法:kruskal和Prim

Kruskal

步驟

基於貪心思想,先把邊從小到大排列,然後按順序選邊並且合並每條邊相連的兩點所在集合(若兩點處於同一集合內,則該邊不必再選),直到所有點處於同一集合為止。

前置知識

並查集

代碼模板
 sort(e+1,e+1+cnt); //按邊權從小到大排序 
for(int i=1;i<=cnt;i++){
int u=e[i].from,v=e[i].to;
if(find(u)!=find(v)){ //Kruskal算法,找到未合並的兩點合並
unite(u,v);
mx=e[i].dis; //更新最大邊
num++;
sum+=e[i].dis;
}
if(num==n-1) break; //可以在連了n-1條邊時即使跳出
}

 

Prim算法

步驟

從任意頂點開始,選擇一個與當前頂點最近的一個頂點,連接兩頂點的邊加入集合中,然後將兩頂點合並成一個點。重複上述操作至點都合並到了一個集合中。

代碼模板

int prim(int graph[][MAX], int n)
{
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++)
{
lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0;
for (i = 2; i <= n; i++)
{
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++)
{
if (lowcost[j] < min && lowcost[j] != 0)
{
min = lowcost[j];
minid = j;
}
}
cout << "V" << mst[minid] << "-V" << minid << "=" << min << endl;
sum += min;
lowcost[minid] = 0;
for (j = 2; j <= n; j++)
{
if (graph[minid][j] < lowcost[j])
{
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return sum;

 

次小生成樹

非嚴格次小生成樹求解方法

設最小生成樹T的權值和為M

只需在未選擇的邊e=(u,v,w)替換原來連接u或v的邊,可得到權值和為M'=M+w-w'的生成樹T‘。對所有替換得到的M’取最小值即可。

求u,v路徑上的邊權最大值

用倍增來維護,處理出每個節點的2^i級祖先以及到達2^i級祖先路徑上最大的邊權,這樣在倍增求LCA的過程中就可以直接求得。

嚴格次小生成樹求解

我們維護到2^i級祖先路徑上的最大邊權的同時維護嚴格次大邊權,當用於替換的邊權的權值與原生成樹中路徑最大邊權相等時,我們用嚴格次大值來替換即可。

時間複雜度O(mlogm)

代碼

//luguo P4180 [BJWC2010]嚴格次小生成樹
#include<bits/stdc++.h>
#define int long long
#define INF 98765432109876543

using namespace std;
const int maxn=3e5+7;

inline void read(int &data){ //快讀優化
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=f*-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
data=x*f;
}

struct node{
int to,w,nxt;
}e[maxn<<2]; //這裏存最小生成樹

struct Node{
int u,v,w;
inline bool operator < (const Node &x)const{ //重定義<運算方便排序
return w<x.w;
}
}a[maxn]; //這是一開始的圖

int n,m,cnt,head[maxn],fa[maxn],sum;
int dep[maxn];
int f[maxn][20]; //存儲祖先信息
int g[maxn][20]; //存儲最大距離
int h[maxn][20]; //存儲次大距離
bool vis[maxn];

void addedge(int u,int v,int w){ //鏈式前向星存圖
e[++cnt]=(node){v,w,head[u]};
head[u]=cnt;
}

int find(int x){ //並查集的查找操作
return x==fa[x]?x:fa[x]=find(fa[x]);
}

void kruskal(){ //得到最小生成樹
int num=0,u,v,w,x,y;
for(int i=1;i<=m;i++){
u=a[i].u,v=a[i].v,w=a[i].w;
x=find(u);y=find(v);
if(x!=y){
vis[i]=1; //錶示這條邊被選中
num++;
fa[x]=y; //合並兩集合
sum+=w; //記錄最小生成樹的權值和
addedge(u,v,w); //構建最小生成樹
addedge(v,u,w);
if(num==n-1) break; //邊數=點數-1跳出
}
}
}

void dfs(int u,int fa,int w){ //倍增來維護每個點的信息
dep[u]=dep[fa]+1; //u點的深度
f[u][0]=fa; //u的上一級父親
g[u][0]=w; //到上一級祖先的邊的最大值
h[u][0]=-INF;//到上一級祖先的邊的次大值
for(int i=1;i<=18;i++){
f[u][i]=f[f[u][i-1]][i-1];
g[u][i]=max(g[u][i-1],g[f[u][i-1]][i-1]);
h[u][i]=max(h[u][i-1],h[f[u][i-1]][i-1]);
if(g[u][i-1]>g[f[u][i-1]][i-1]) h[u][i]=max(h[u][i],g[f[u][i-1]][i-1]); //替換次大值
else if(g[u][i-1]<g[f[u][i-1]][i-1]) h[u][i]=max(h[u][i],g[u][i-1]);
}
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to,w=e[i].w;
if(v==fa) continue;
dfs(v,u,w);  //遍曆下一個節點
}
}

int LCA(int x,int y){ //lca求公共祖先
if(dep[x]<dep[y]) swap(x,y); //x的深度比y大
for(int i=15;i>=0;i--){
if(dep[f[x][i]]>=dep[y]) x=f[x][i];  //拉近到同一深度
}
if(x==y) return x; //y是x的祖先,直接返回
for(int i=15;i>=0;i--){
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];//同時向上跳
}
return f[x][0];
}

int get(int u,int v,int mx,int ans=-INF){
for(int i=18;i>=0;i--){
if(dep[f[u][i]]>=dep[v]){
if(mx!=g[u][i]) ans=max(ans,g[u][i]); //比較ans和u跳2^i路徑的最大值
else ans=max(ans,h[u][i]);//比較ans和u跳2^i路徑的次大值
u=f[u][i]; //往上跳
}
}
return ans;
}

void output(){
int u,v,w,lca,x,y,ans=INF;
for(int i=1;i<=m;i++){
if(vis[i]) continue; //如果是最小生成樹上的邊直接跳過
u=a[i].u,v=a[i].v,w=a[i].w,
lca=LCA(u,v); //找到這兩點的LCA
x=get(u,lca,w); //獲取u到lca的最大邊權
y=get(v,lca,w);
ans=min(ans,sum-max(x,y)+w); //最小生成樹權值和-所選最大邊+新邊
}
for(int i=1;i<=m;i++){
if(vis[i]) continue;
u=a[i].u,v=a[i].v,w=a[i].w,lca=LCA(u,v);
x=get(u,lca,w);
y=get(v,lca,w);
ans=min(ans,sum-max(x,y)+w);
}
printf("%lld",ans);
}

signed main(){
read(n);read(m);
for(int i=1;i<=n;i++) fa[i]=i; //一開始父親指向自己
for(int i=1;i<=m;i++){
read(a[i].u);read(a[i].v);read(a[i].w);
} //存圖
sort(a+1,a+1+m); //對邊排序
kruskal(); //最小生成樹
dfs(1,0,0); //以1為根遍曆這棵樹
output();
return 0;
}

 

最小生成樹計數

根據最小生成樹的兩個性質:

(1)不同的最小生成樹中,每種權值的邊出現的個數都是確定的。

(2)不同的生成樹中,某一種權值的邊連接完成後,形成的連通塊狀態是一樣的。

那麼我們可以把每種權值的處理看成是分開的好幾步,將得到的結果相乘。

將已經計算好的連通塊縮成一個點,那麼就變成了一個獨立的圖的生成樹問題,可以用矩陣樹定理來求解

矩陣樹定理(Kirchhoff‘s Matrix Tree Theorem)

聲明:無論有向無向,都允許重邊,不允許自環。
解决了:一張圖中生成樹計數問題
前置知識:線性代數

圖的生成樹數量等於調和矩陣的行列式。

矩陣-樹定理(matrix-tree theorem)是一個計數定理.若連通圖G的鄰接矩陣為A,將A的對角線(i,i)元素依次換為節點i的度d(i),其餘元素(i,j) (j!=i) 取Aij的相反數,所得矩陣記為M,則M的每個代數餘子式相等,且等於G的生成樹的數目.這就是矩陣一樹定理.我們常常稱矩陣M為基爾霍夫矩陣。

 

基爾霍夫Kirchhoff矩陣 K =度數矩陣 D - 鄰接矩陣 A

  • 對於一個無向圖 G ,它的生成樹個數等於其基爾霍夫Kirchhoff矩陣任何一個N-1階主子式的行列式的絕對值。

  • 已經得出了基爾霍夫Kirchhoff矩陣,那麼隨便去掉某一行一列並計算出新矩陣的行列式,其絕對值即為生成樹個數。

    image

 

算法思想

利用圖的Kirchhoff矩陣,可以在O(n^3)時間內求出生成樹的個數。

行列式計算(模板)

通過行列式的變換,複雜度可以優化到O(n^3)

 for(int i=1;i<cnt;i++){  //下面是把矩陣轉化為上三角的形式 
int j;
for(j=i;j<cnt;j++){
if(sq[j][i]) break;  
}
if(j==cnt) continue; //這一行全為0
if(j!=i){
for(int k=0;k<=cnt;k++) swap(sq[i][k],sq[j][k]); //對兩行進行交換
ans*=-1; //行列式的值取相反數
}
for(j=i+1;j<cnt;j++){ //上三角(對同一列其他行的元素化0處理)
while(sq[j][i]){
int t=sq[j][i]/sq[i][i];
for(int k=i;k<cnt;k++){
sq[j][k]=(sq[j][k]-sq[i][k]*t%mod+mod)%mod; //更新該行
}
if(!sq[j][i]) break; //對角化0
for(int k=i;k<cnt;k++){
swap(sq[i][k],sq[j][k]); //交換兩行
}
ans*=-1; //取反
}
}
}
for(int i=1;i<cnt;i++){
ans*=sq[i][i]; //行列式計算:乘對角元素
ans%=mod;
}

建議去看高斯-約旦消元的模板。

 

其他待更新

Kruskal重構樹
最小瓶頸路
瓶頸生成樹
Boruvka算法

可能會再出一章,因為目前還不是很必要學。

 

參考資料

https://blog.csdn.net/yeruby/article/details/38615045

https://blog.csdn.net/clover_hxy/article/details/69397184

https://www.cnblogs.com/zj75211/p/8039443.html

https://www.cnblogs.com/yangsongyi/p/10697176.html

https://www.cnblogs.com/zj75211/p/8039443.html

OI-wiki

百度百科

版权声明:本文为[LINNO]所创,转载请带上原文链接,感谢。 https://gsmany.com/2021/08/20210815175349232S.html