Tarjan算法

2022年11月4日 47点热度 0人点赞 0条评论

Tarjan 算法

Tarjan 算法是基于深度优先搜索的算法, 用于求解图的连通性问题. Tarjan 算法可以在线性时间内求出无向图的割点与桥, 进一步地可以求解无向图的双连通分量; 同时, 也可以求解有向图的强连通分量, 必经点与必经边.

Tarjan 是谁?

提到 Tarjan, 不得不提的就是算法的作者 Robert Tarjan. 他是一名著名的计算机科学家, 我们耳熟能详的最近公共祖先 (LCA) 问题, 强连通分量问题, 双连通分量问题的高效算法都是由他发现并解决的, 同时他还参与了开发斐波那契堆, 伸展树的工作.

Tarjan 的主页

file

概念介绍

  • 割点: 若从图中删除节点 $x$ 以及所有与 $x$ 关联的边之后, 图将被分成两个或两个以上的不相连的子图, 那么称 $x$ 为图的割点.
  • 桥: 若从图中删除边 $e$ 之后, 图将分裂成两个不相连的子图, 那么称 $e$ 为图的桥或割边.
  • 时间戳: 时间戳是用来标记图中每个节点在进行深度优先搜索时被访问的时间顺序, 当然, 你可以理解成一个序号 (这个序号由小到大), 用 $dfn[x]$ 来表示.
  • 搜索树: 在无向图中, 我们以某一个节点 $x$ 出发进行深度优先搜索, 每一个节点只访问一次, 所有被访问过的节点与边构成一棵树, 我们可以称之为无向连通图的搜索树.
  • 追溯值: 追溯值用来表示从当前节点 $x$ 作为搜索树的根节点出发, 能够访问到的所有节点中, 时间戳最小的值 $low[x]$. 那么, 我们要限定下什么是能够访问到的所有节点? 其需要满足下面的条件之一即可:
    • 以 $x$ 为根的搜索树的所有节点
    • 通过一条非搜索树上的边, 能够到达搜索树的所有节点

无向图的桥判定法则

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

它代表的是节点 $u$ 被访问的时间, 要小于以下这些节点被访问的时间: $low[v]$ .

  • 以节点 $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];             // 图的前向星表示
int ver[SIZE * 2];          // 记录顶点
int Next[SIZE * 2];         // 记录边
int dfn[SIZE];              // dfn[x] 代表节点 x 对应的时间戳
int low[SIZE];              // low[x] 代表节点 x 的追溯值
int n;                      // 图的节点的个数
int m;                      // 图中边的个数
int tot;                    // 节点的序号
int 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) {
    // 在搜索之前, 先初始化节点 x 的时间戳与追溯值
    dfn[x] = low[x] = ++num;
    // 图的前向星型表示法的遍历
    // 通过 head 变量获取节点 x 的直接连接的第一个相邻节点的序号
    // 通过 Next 变量, 迭代获取剩下的与节点 x 直接连接的节点的序号
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];                           // 此时, i 代表节点 y 的序号
        if (! dfn[y]) {                           // 如果当前节点 y 没有被访问过
            tarjan(y, i);                         // 递归搜索以 y 为根的子树
            low[x] = min(low[x], low[y]);         // 计算 x 的追溯值
            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]);
        }
    }
}

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]);
}

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

首先, 我们先明确下$y$ 不是 $x$ 的父节点的情况是什么?

以 $x'$ 节点出发进行深度优先搜索, 紧接着搜索到节点 $x$. 此时, 以 $x$ 为根进行递归搜索, 计算出其下一个节点为 $y$. 如果此时 $y$ 与 $x'$ 是一个节点的话 —— $y$ 是 $x$ 的父节点, 需要忽略这种情况对于追溯值的计算.

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

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

  • 如果 x 为偶数 (2), 那么 $x \wedge 1 = 2 \wedge 1 = 3$
  • 如果 x 为奇数 (3), 那么 $x \wedge 1 = 3 \wedge 1 = 2$

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

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

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

file

我自己用邻接链表实现的

class Solution {

private:
    const int maxn = 100000;

    vector<int> dfn = vector<int>(maxn);                    // 节点访问的顺序
    vector<vector<int>> graph = vector<vector<int>>(maxn);  // 邻接列表
    int start = 0;
    vector<vector<int>> bridge = vector<vector<int>>();

public:

    int tarjan(int curr, int prev) {

        int currLow = ++start;
        dfn[curr] = currLow;

        // 遍历邻居节点
        for(int nei : graph[curr]) {
            // nei 还没有访问, dfn 所有元素的默认值都是 0, 所以 ! dfn[nei] 为真说明 nei 还没访问过
            if (! dfn[nei]) {
                // nei 还没访问过的话, 就以 nei 为根节点继续找
                int neiLow = tarjan(nei, curr);
                // 计算 curr 的追溯值
                currLow = min(currLow, neiLow);
                // 出现这种请情况表示从 curr 可以到 nei, 但是 nei 永远回不去 curr 了
                if (neiLow > dfn[curr]) {
                    bridge.push_back({curr, nei});
                }
            } else if (nei != prev) {
                // 此时 nei 是已经访问过的, 从 nei 开始回溯
                currLow = min(currLow, dfn[nei]);
            }
        }

        return currLow;
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {

        // 初始化 start
        start = 0;

        // 构造邻接列表
        for (auto& c : connections) {
            graph[c[0]].push_back(c[1]);
            graph[c[1]].push_back(c[0]);
        }

        tarjan(0, -1);
        return bridge;
    }
};

leetcode 上大佬的实现

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;

class Solution {
public:
    vector<vector<int>> ans;
    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
    }

    void tarjan(int u, int from) {
        dfn[u] = low[u] = ++ timestamp;
        for (int i = h[u]; ~i; i = ne[i]) {
            int j = e[i];
            if (! dfn[j]) {
                tarjan(j, i);
                low[u] = min(low[u], low[j]);
                if (dfn[u] < low[j]) ans.push_back({u, j});
            } else if (i != (from ^ 1)) {
                low[u] = min(low[u], low[j]);
            }
        }
    }

    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        memset(h, -1, n * 4);
        memset(dfn, 0, n * 4);
        idx = timestamp = 0;

        for (auto& p: connections) {
            int a = p[0], b = p[1];
            add(a, b), add(b, a);
        }

        tarjan(0, -1);
        return ans;
    }
};

file

rainbow

没什么大用的码农; 贴图怪; bug制造者; 只会电脑开关机的开发;

文章评论