SkyWT / 博客 / Tarjan 算法求解无向图的割点与割边

Tarjan 算法求解无向图的割点与割边

2018 年 8 月 5 日 09:47


文章目录

在一幅无向图中,如果删除了一个点,导致图分成了两个或多个联通块(强连通分量),那么这个点就是割点。怎么求这样的点呢?最原始暴力的方法就是每次枚举一个点,删除,跑一遍最短路。今天我们可以用更高级的 Tarjan 算法 Θ(N)\displaystyle \Theta (N) 求解。

割点与割边

割点的定义

在一个无向图中,如果有一个顶点集合,删除这个顶点集合以及这个集合中所有顶点相关联的边以后,图的连通分量增多,就称这个点集为割点集合。

也就是前文所述:如果删除了一个点,导致图分成了两个或多个联通块(强连通分量),那么这个点就是割点(也叫作割顶)。说得再通俗点,去掉割点,图会不连通。

割边的定义

与割点类似:

假设有连通图 G,e 是其中一条边,如果 G-e 是不连通的,则边 e 是图 G 的一条割边。

就是说如果把这条边删除,图分为两个强连通分量,这条边就称为割边(也称为桥)。

暴力求解

以割点为例:前面也提到了,最原始的暴力方法:就是每次枚举一个点,删除,跑一遍最短路,看看结点 1 是否还可以到达除了删除点之外的所有点,如果不能则说明删除点是割点。如果跑最稳的 Dijkstra+Heap,复杂度也要 Θ(NMlog2(M))\Theta (N\ast M \ast log_2(M))……

Tarjan 算法

求解割点和割边,用 Tarjan 算法会十分优秀。在此之前我们要先学习下什么是 DFS 树。

DFS 树

所谓 DFS 树,就是对一幅图进行 DFS 按照 DFS 顺序得到的一棵生成树。可以从任意点开始 DFS(一般从 1 开始),并不影响答案。在这幅图中,在 DFS 树中的边称为树边,不在 DFS 树中的边称为非树边。

返祖边

这里我们只研究无向图。在无向图中,非树边只会以返祖边的形式存在。也就是说非树边会从当前点指向某个祖先。例如下图中,D 指向 A 的边就是返祖边。(这张图其实是无向图,为了便于理解,按照 DFS 的顺序标出方向)

graph TB
    A((A))-->B((B))
    B((B))-->C((C))
    B((B))-->D((D))
    D((D))-->A

算法原理

割点的求解

可以把割点分为两种情况:

  1. 根节点在 DFS 树中有多于一个子节点,那么根节点就是割点;
  2. 对于非根节点 u,它至少有一棵子树没有返祖边可以到达 u 的祖先。

第一种情况很好理解;对于第二种情况,如果 u 有一个子树中有一个结点 x 有返祖边可以到达 u 的祖先,那么把 u 删除后,由于原来的树是联通的,那么我们找出的 x 仍然有边可以到达 u 以上的所有点,又因为那个点在 u 的一棵子树里,那么这棵子树就可以到达 u 以上的所有点!

割边的求解

割边甚至更加简单,忽略第一种情况,如果一条边是割边,当且仅当其子树均没有跨过这条边。

具体实现

以求割点为例,每个节点维护几个信息:

  • dfn(x)dfn(x) 表示点 x 的标号,即它是第几个被遍历到的点。维护这一信息十分有用,因为如果点 a 是点 b 的祖先,那么 dfn(a)<dfn(b)dfn(a) \lt dfn(b)

  • low(x)low(x) 表示 x 点不经过其的父节点,能通过返祖边到达的 dfndfn 最小的祖先的 dfndfn 值。初始值为 dfn(x)dfn(x)

  • fa(x)fa(x) 表示 x 的父节点。在求割边时,我们记录的 fa(x)fa(x) 表示 x 与其祖先之间的边的标号。

在 DFS 的同时可以维护这几个信息,回溯时判断如果 low(v)>dfn(x)low(v)>dfn(x) (v 是 x 的儿子)说明 x 是割点。

核心代码如下:

inline void DFS(int x){
    vis[x]=1;dfn[x]=low[x]=++acnt;
    int nowson=0;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        nowson++;
        fa[son[i]]=x;
        DFS(son[i]);
        low[x]=min(low[x],low[son[i]]);
        if (x!=1&&low[son[i]]>dfn[x]) ans[x]=true;
        if (x==1&&nowson>=2) ans[x]=true;
    } else if (son[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]);
}

例题

割点模板题

POJ1144 Network

割边模板题

ZOJ2588 Burning Bridges

参考代码

割点(POJ1144)

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=105,maxe=1000005;
int n,fa[maxn];
int tot=0,acnt=0,dfn[maxn],low[maxn];
int lnk[maxn],nxt[maxe],son[maxe];
bool vis[maxn],ans[maxn];
inline void add(int x,int y){
    tot++;son[tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
    tot=0;acnt=0;
    memset(fa,0,sizeof(fa));
    memset(lnk,0,sizeof(lnk));
    memset(nxt,0,sizeof(nxt));
    memset(son,0,sizeof(son));
    memset(vis,0,sizeof(vis));
    memset(dfn,0,sizeof(dfn));
    memset(ans,0,sizeof(ans));
}
inline void DFS(int x){
    vis[x]=1;dfn[x]=low[x]=++acnt;
    int nowson=0;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        nowson++;
        fa[son[i]]=x;
        DFS(son[i]);
        low[x]=min(low[x],low[son[i]]);
        if (x!=1&&low[son[i]]>=dfn[x]) ans[x]=true;
        if (x==1&&nowson>=2) ans[x]=true;
    } else if (son[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]);
}
int main(){
    for (;;){
        scanf("%d",&n);if (n==0) break;
        Init();int ans_cnt=0;
        int x;scanf("%d",&x);
        while (x!=0){
            int now=0;char ch=getchar();
            while (ch!=10&&ch!=13){
                while ((ch<'0'||ch>'9')&&ch!=10&&ch!=13) ch=getchar();
                if (ch==10||ch==13) break;
                while (ch>='0'&&ch<='9') now=now*10+ch-'0',ch=getchar();
                add(x,now);add(now,x);
                now=0;
            }
            scanf("%d",&x);
        }
        DFS(1);
        for (int i=1;i<=n;i++) ans_cnt+=ans[i];
        printf("%d\n",ans_cnt);
    }
    return 0;
}

割边(ZOJ2588)

#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
const int maxn=10005,maxe=200005;
int T,n,m,fa[maxn];
int tot=0,acnt=0,dfn[maxn],low[maxn];
int lnk[maxn],nxt[maxe],son[maxe],id[maxe];
bool vise[maxe],ans[maxe],vis[maxn];
vector<int> que_ans;
inline void add(int x,int y,int z){
    tot++;son[tot]=y;id[tot]=z;nxt[tot]=lnk[x];lnk[x]=tot;
}
inline void Init(){
    tot=0;acnt=0;que_ans.clear();
    memset(fa,0,sizeof(fa));
    memset(id,0,sizeof(id));
    memset(lnk,0,sizeof(lnk));
    memset(nxt,0,sizeof(nxt));
    memset(son,0,sizeof(son));
    memset(dfn,0,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(ans,1,sizeof(ans));
    memset(vis,0,sizeof(vis));
}
inline void DFS(int x){
    dfn[x]=low[x]=++acnt;
    for (int i=lnk[x];i;i=nxt[i]) if (!vis[son[i]]){
        fa[son[i]]=id[i];vis[son[i]]=true;
        DFS(son[i]);
        if (low[son[i]]<=dfn[x]) ans[id[i]]=false;
        low[x]=min(low[x],low[son[i]]);
    } else if (id[i]!=fa[x]) low[x]=min(dfn[son[i]],low[x]),ans[id[i]]=false;
}
int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%d%d",&n,&m);
        Init();
        for (int i=1;i<=m;i++){
            int x,y;scanf("%d%d",&x,&y);
            add(x,y,i);add(y,x,i);
        }
        vis[1]=true;DFS(1);
        
        for (int i=1;i<=m;i++) if (ans[i]) que_ans.push_back(i);
        int nn=que_ans.size();printf("%d\n",nn);
        for (int i=0;i<nn-1;i++) printf("%d ",que_ans[i]);
        if (nn!=0) printf("%d\n",que_ans[nn-1]);
        // printf("LOW: ");for (int i=1;i<=n;i++) printf("%d ",low[i]);printf("\n");
        // printf("DFN: ");for (int i=1;i<=n;i++) printf("%d ",dfn[i]);printf("\n");
        if (T>0) printf("\n");
    }
    return 0;
}

参考

割点_百度百科
割边_百度百科

吐槽一下,POJ1144 调代码一直调不对,然后去 discuss 区搞了组数据,用 Mermaid 生成图,我以为会很清晰,结果是这样的……

graph TB;
17---4
17---18
1---11
7---5
13---1
3---1
14---5
15---20
9---12
6---8
16---14
18---8
8---4
20---18
20---10
2---3
12---5
5---9
5---20
19---20
19---9
19---11
19---2
11---3
4---15
10---3
21---3

吐血……


暂无评论


发表新的评论

所有评论都将经过博主审核。请勿填写无意义邮箱或发表无关评论、广告等,否则会被视为垃圾评论。

提交评论即表明你同意本网站使用 Cookie,并允许本站在后台记录你的邮箱、IP 地址等必要信息。这些信息不会被透露给其他用户。(提交一次评论后,本提示将不再展示)