Tarjan

yx666 · 2024-10-19 15:13:28 · 算法·理论

Tarjan 算法

算法总览

Tarjan 算法是图论中非常常用的算法之一，能解决强连通分量，双连通分量，割点和桥，求最近公共祖先（LCA）等问题。

核心：

Tarjan 算法是基于深度优先搜索的，用于求解图的连通性问题的算法。

搜索树

在无向图中，我们以某一个节点 x 出发进行深度优先搜索，每一个节点只访问一次，所有被访问过的节点与边构成一棵树，我们称之为“无向连通图的搜索树”。

时间戳 dfn[]

时间戳是用来标记图中每个节点在进行深度优先搜索时被访问的时间顺序，可以理解成一个序号（由小到大），用 dfn[x] 来表示。

回溯值 low[]

回溯值用来表示以当前节点 x 为根的搜索树，能够访问到的所有节点中，时间戳最小的值 —— low[x]。

“搜索树能够访问到的节点 y”需要满足下面的任意一个条件：

在上面的计算过程中，我们可以认为以序号 2 为根的搜索树的节点有 \{2,3,4,5\}，能够访问到的节点有 \{1,2,3,4,5\}，(1,5) 这条边为上面所说的“非树边”。

PS：动画下载链接，直接点右上角下载。

【勘误】：low[7] 应该等于 6，low[6] 应该等于 1。

这是无向图：

vector<int>e[N];
int low[N],dfn[N],tot;
void tarjan(int x){
    low[x]=dfn[x]=++tot;
    for(auto y:e[x]){
        if(!dfn[y]){        // y 在以 x 为根的搜索树上。
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else{              // x 与 y 直接通过一条非树边相连，且 x 在以 y 为根的搜索树上
            low[x]=min(low[x],dfn[y]);
        }
    }
}

这是有向图：

vector<int>e[N];
bitset<N>intr;
stack<int>tr;
int tot,dfn[N],low[N];
void tarjan(int x){
    dfn[x]=low[x]=++tot;
    tr.emplace(x);
    intr[x]=true;

    for(int y:e[x]){
        if(!dfn[y]){                    // y 在以 x 为根的搜索树上。
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }else if(intr[y]){              // x 与 y 直接通过一条非树边相连，且 x 在以 y 为根的搜索树上
            low[x]=min(low[x],dfn[y]);
        }
    }

    if(dfn[x]==low[x]){
        int y;
        do{
            intr[y=tr.top()]=false;tr.pop();
        }while(y!=x);
    }
}

注意两种图判断“x 与 y 直接通过一条非树边相连，且 x 在以 y 为根的搜索树上”的条件。

例题：缩点

To be continued…

求解图的割点与桥

割点与桥介绍

割点

若从图中删除节点 x 以及所有与 x 关联的边之后，图将被分成两个或两个以上的不相连的子图，那么称 x 为图的 割点。

桥

若从图中删除边 e 之后，图将分裂成两个不相连的子图，那么称 e 为图的 桥 或 割边。

代码详解

在了解了 Tarjan 算法的基本概念与操作流程之后，我们来看看具体的代码。这里推荐大家学习一篇 GitHub 上介绍 Tarjan 算法 的文章（来自 李煜东 的《算法竞赛进阶指南》）。

无向图的桥判定法则

在一张无向图中，判断边 e（其对应的两个节点分别为 u 与 v）是否为桥，需要其满足如下条件即可：dfn[u] < low[v]

它代表的是节点 u 被访问的时间，要优先于（小于）以下这些节点被访问的时间：

• 以节点 v 为根的搜索树中的所有节点

• 通过一条非搜索树上的边，能够到达搜索树的所有节点（在回溯值内容中有所解释）

是不是上面的两个条件很眼熟？对，其实就是前文提到的回溯值 —— low[v]。

C++ 实现

// tarjan 算法求无向图的桥
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE];
int n, m, tot, num;
bool bridge[SIZE * 2];

void add(int x, int y) {
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (in_edge ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
}

int main() {
    // [[0,1],[1,2],[2,0],[1,3]]
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    for (int i = 2; i < tot; i += 2)
        if (bridge[i])
            printf("%d %d\n", ver[i ^ 1], ver[i]);
}

首先，我们来看看变量的含义。

const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE];
int n, m, tot, num;
bool bridge[SIZE * 2];

• SIZE —— 节点的个数，可以基于实际的节点个数增加一些冗余度。
• 关于 head/Next/ver 变量的介绍，可以参阅下面的动画配合理解。
• 假设场景，有一个节点 u，以及其直接相连的若干节点 v_1，v_2，v_3。
• head[u] 代表节点 u 直接相邻的第一个节点 v_1 的序号 tot1。
• Next[tot1] 代表节点 u 直接相邻的下一个节点的序号 tot2。
• ver[tot1] 代表序号为 tot1 的节点的值（v_1）。
• dfn[x] 代表节点 x 对应的时间戳，low[x] 代表节点 x 的回溯值。
• bridge[tot] 代表序号为 tot 的边是否为桥。

针对于 head、Next、ver 变量的关系还是比较难懂。那么，我们用图像的方式，把节点 u、v_1、v_2 与 v_3 画出来看看。

通过上图我们可以形象地理解这三个变量之间的关系。那么，针对于 add 方法，想必也可以很顺利地想明白 —— 建立并维护节点 x、y 形成的边。

接着，我们看看 Tarjan 算法的主体：

// x 代表当前搜索树的根节点，in_edge 代表其对应的序号（tot）
void tarjan(int x, int in_edge) {
    // 在搜索之前，先初始化节点 x 的时间戳与回溯值
    dfn[x] = low[x] = ++num;
    // 通过 head 变量获取节点 x 的直接连接的第一个相邻节点的序号
    // 通过 Next 变量，迭代获取剩下的与节点 x 直接连接的节点的序号
    for (int i = head[x]; i; i = Next[i]) {
        // 此时，i 代表节点 y 的序号
        int y = ver[i];
        // 如果当前节点 y 没有被访问过
        if (!dfn[y]) {
            // 递归搜索以 y 为跟的子树
            tarjan(y, i);
            // 计算 x 的回溯值
            low[x] = min(low[x], low[y]);
            // 桥的判定法则
            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true; // 标记当前节点是否为桥（具体见下文）
        }
        else if (i != (in_edge ^ 1)) // 当前节点被访问过，且 y 不是 x 的“父节点”（具体见下文）
            low[x] = min(low[x], dfn[y]);
    }
}

语句详解

语句一：i != (in_edge ^ 1)

首先，我们先明确下“y 不是 x 的父节点”的情况是什么？

PS：这有一个视频：链接，直接点右上角下载。

如上面视频的过程，以 x\rq 节点出发进行深度优先搜索，紧接着搜索到节点 x。

此时，以 x 为根进行递归搜索，计算出其下一个节点为 y。如果此时 y 与 x\rq 是一个节点的话 ——y 是 x 的“父节点”，需要忽略这种情况对于回溯值的计算。

我们知道，在建立边的关系时（add），我们为每一条边的两个节点创建了两个相邻的序号值。又因我们 tot 是从 2 开始计数的，故每一条边的两个节点的序号肯定是 一奇一偶，偶数为小。比如，2 与 3，4 与 5，而不会出现 5 与 6 这样的情况。

在明确了上面的情况之后，我们看看一个数 x 与 1 进行异或的结果是什么？

• 如果 x 为偶数（2），那么 x ^ 1 = 2 ^ 1 = 3。
• 如果 x 为奇数（3），那么 x ^ 1 = 3 ^ 1 = 2。

最后，我们来想想如何判定两个点是否属于一条边的两个端点？是不是只要满足 a ^ 1 == b 条件，那么 a 与 b 就是一条边的两个端点了？对，就是这样！

语句二：bridge[i] = bridge[i ^ 1] = true

这句话是为了标记某个节点对应的边是桥。而又因为我们在建立边时是成对地，那么相邻的两个节点都应该被标记。

模版题

参考文章

• 图片来源。