60分钟搞定Tarjan算法求解无向图的割点与桥

关注
60分钟搞定Tarjan算法求解无向图的割点与桥www.shan-machinery.com

本人在学习 Tarjan 算法求解无向图的割点与桥的问题时,很快发现了一篇简洁易懂的文章。很顺利地了解算法的思路,并写出了“高效”的代码,此时内心飘过 —— So Easy。然而,当我翻开《算法竞赛进阶指南》这本书的有关篇章时,我发现其中经过精简优化的代码有几条语句让我不得其所。以至于,花了较多心思和时间来思考🤔这段真正高效的 Tarjan 算法的工作原理以及代码的编写。

关于 Tarjan 算法,我将会写若干篇系列文章,来完整系统地介绍 Tarjan 算法的原理以及其主要解决的问题。而在本章我主要讲一个问题 —— 如何使用 Tarjan 算法求解无向图的割点与桥。

在讲述问题之前,我们先来简单地了解下什么是 Tarjan 算法?

Tarjan 算法

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

如果,你对上面的一些术语不是很了解,那么也毫无关系。目前为止,我们只要知道 Tarjan 算法是基于深度优先搜索的,用于求解图的连通性问题的算法就好了。

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

无向图的割点与桥

首先,什么是无向图?简单说,若一个图中每条边都是无方向的,则称为无向图。

割点

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

无向图的割点无向图的割点桥

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

无向图的桥无向图的桥如何求解图的割点与桥?

那么,在了解了 Tarjan 算法的背景以及图的割点与桥的基本概念之后,我们下面所面临的问题就是 —— 如何求解图的割点与桥?

在这里,我们开门见山,直接引出 Tarjan 算法在求解无向图的割点与桥的工作原理。

时间戳

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

搜索树

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

追溯值

追溯值用来表示从当前节点 x 作为搜索树的根节点出发,能够访问到的所有节点中,时间戳最小的值 —— low[x]。那么,我们要限定下什么是“能够访问到的所有节点”?,其需要满足下面的条件之一即可:

以 x 为根的搜索树的所有节点通过一条非搜索树上的边,能够到达搜索树的所有节点

是的,你可能觉得这段话太绕了,那么我们通过动画的方式来摸你追溯值真实计算过程。

Tarjan 算法 —— 追溯值的计算过程

在上面的计算过程中,我们可以认为以序号 2 为根的搜索树的节点有 \{2,3,4,5\}。上面所说的“通过一条非搜索树上的边”可以理解成动画中的 (1, 5) 这条边,“能够到达搜索树的所有节点”即为节点 1。

Tarjan —— 追溯值的计算过程代码详解

在了解了 Tarjan 算法的基本概念与操作流程之后,我们来看看具体的代码。说实话,在看到这一份李煜东大佬写的代码时,尽管我知道 Tarjan 在求解无向图的桥与割点的思路,也知道每一条代码语句的含义,但就是不知道为什么这样写能搞达到要求的效果。也就是说,这份代码是经过精心设计与优化后的代码。

无向图的桥判定法则

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

dfn[u] < low[v]

它代表的是节点 u 被访问的时间,要优先于(小于)以下这些节点被访问的时间 —— low[v]。

以节点 v 为根的搜索树中的所有节点通过一条非搜索树上的边,能够到达搜索树的所有节点(在追溯值内容中有所解释)

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

Code// tarjan 算法求无向图的桥#include#include#include#include#includeusing 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 https://www.shan-machinery.com