史上最清晰的 Tarjan 算法详解

摘要：图的算法是进行静态分析的基础数据算法，如何提高图的分析效率，就需要对图的算法有进一步的认识。

1. 引言

在静态分析技术中, 我们常用会将代码转成抽象语法树(AST), 然后采用深度遍历（DFS）来完成对语法树的遍历和查询，找到潜在的问题缺陷。

对于语义的分析，我们采用的控制流和数据流也都无一例外的采用了以图为基础的算法, 通过图的可达性, 来完成变量、表达式的可达分析, 以及变量的依赖分析、值流图等等。

图的算法是进行静态分析的基础数据算法，如何提高图的分析效率，就需要对图的算法有进一步的认识。

1.1. 故事从 1986 年的图灵奖说起

1986 年的图灵奖是 John E.Hoperoft 和 Robert E·Tarjan 两人共同获得， 而且 Robert E·Tarjan 曾是 John E.Hoperoft 的学生,他们的密切合作取得了算法设计与分析方面的卓越贡献, 赢得了 1986 年度美国计算机协会（Association for Computing Machinery, ACM）图灵奖的荣誉。

image

1.2. 故事的前半段

在领奖的时候，John E.Hopcroft 做了一个“计算机科学:一门学科的出现” 的演讲， 从他自己的经历出发，展现了计算科学在那个风起云涌的年代形成的过程。

时间回到 1964 年，计算机才刚刚成为一门学科， 普林斯顿大学一个偶然的邀请，使本打算到美国西海岸教授电器工程的 Hoperoft 改变了自己的人生轨迹，从此投入到了计算机科学的研究。

那个时候，计算机科学的大部分课程的内容都是围绕着数字计算机电路的设计以及如何减少构造这些电路所需要的晶体管数展开的。然而, 到了六十年代中期, 技术的进步已使得晶体管马上就要被每片有多达几百个元件的计算机芯片所取代。因此, 减少晶体管数再没有么意义，那时所谓的计算机科学的课程即将过时, 必须发展新的课程。

Hopcroft 并没有接受过正规计算机教育，只是他在斯坦福大学读电器工程学博士的时候，上过 David Huffman（霍夫曼编码的发明者）教的一门计算机课程，学习了开关电路、逻辑设计以及计算理论的基本知识。普林斯顿要 Hoperoft 在自动机理论方面开设一门新的课程，当时没有任何教程可以参考, 只给了他推荐了 6 篇论文。 其中包括：

• 1943 年,McCulloch 和 Pitts 发表的一篇关于用来描述神经网络中活动的逻辑演算的论文。这些活动是一系列的电脉冲, 并能看作是 0-1 串。论文提出了一种描述神经网中的 0-1 串是如何结合以产生新的 0-1 串的方法。这种描述方法后来被发展成为一种描述串集的正则表达式语言。

• 数学家 Michael Rabin 和 Dana Scott 提出的一种具有有限量存储其的计算机模型，这个模型就是有限状态自动机。并证明了有限状态自动机的可能的行为和正则表达式所描述的行为的一致性。 数学和计算机学思想的汇集，使计算机科学家相信正则语言和有限自动机的重要性。

• 语言学家 Chomsky 研究发展的一种前后文无关文法的概念。这与 Backus 和 Naur 为描述各种程序设计语言的语法而发展的一套形式表示法惊人的等价。

• 图灵于 1963 年引入了一种简单的计算装置模型,现在称做图灵机。并论证了能够进行的任何计算过程都能在图灵机上编程序实现。图灵机是现代可计算理论的基础。

• 数学家 Hartmanis 和 Stearns 采用算法的执行步数来度量算法的复杂性，并使这一方法发展了一种复杂性分类的理论。

1967 年，Hopcroft 转去康奈尔大学，转而研究算法与数据结构。他相信理论计算机科学的方法学，可以用来为算法设计发展一种科学基础,这对于实践者将是很有用的。

在七十年代初期, Hopcroft 在斯坦福大学度过了一年的假期, 在那里遇到 Robert Tarjan 并与他同用一间办公室, Tarjan 那时是二年级研究生。获得这次图灵奖的研究就是在那段合作时间里作的。

Hopcroft 在发言的最后，还不忘呼吁，为了保持美国取得的技术和经济的领导地位，必须对计算机科学进行全国性的投入和支持。

1.3. 故事的后半段

说到 Tarjan，他在图论算法和数据结构领域有很大的贡献。 下面对这个大牛也做个简单的介绍。

Tarjan 在 1969 年获得了加州理工学院数学学士学位。在斯坦福大学，他获得了他的计算机科学硕士学位（1971）和博士学位(1972). Tarjan 从 1985 年开始任教于普林斯顿大学。

Tarjan 还拥有很多研究所和公司的工作经验， 例如：AT&T 贝尔实验室、NEC 研究所、InterTrust Technologies、康柏、惠普、微软等。

Tarjan 是一个非常高产的计算机科学家，从计算机科学出版物在线参考网站 dblp 收集的有关他发表在的杂志、会议和出版物，多达 300+。

他独立研究的算法有：Tarjan 离线的 LCA 算法（一种优秀的求最近公共祖先的线性离线算法）、Tarjan 强连通分量算法（甚至比后来才发表的 Kosaraju 算法平均要快 30%）、Hopcroft-Tarjan 算法（第一个平面性测试的线性算法）。

他还开发了一些重要的数据结构，比如斐波那契堆（Fibonacci Heap，插入查询合并 O(1)，删除 O(logn)的强大数据结构）、伸展树（Splay Tree，和另外一位计算机科学家共同发明）、动态树（Link-Cut Tree，发明人之一）。

下图是他普林斯顿大学个人简介中的一个插图， 这个是他的另一个重要的研究领域：自适应搜索树的查询(self-adjusting search tree)，在树的遍历过程中，改变树的结构以提高树的搜索效率。

image

他的主要荣誉：

• 1986 年，与 John Hopcroft 分享了当年的图灵奖，原因是对算法和数据结构的设计分析做出的地基式的贡献；

• 1994 年，被选为美国计算机协会（Association for Computing Machinery, ACM）院士；

• 2004 年，欧洲科学院的 Blaise Pascal 数学和计算机科学奖章；

• 1983 年，Rolf Nevanlinna 奖的第一个获奖者，国际数学联盟在信息科学的数学方面的杰出贡献而每四年获奖一次；

2. Tarjan 算法

图的一些基本概念：

• 关联（incident）：点为边的端点;

• 邻接（adjacent）：点与点关联同一条边，或边与边关联同一顶点；

• 子图：图 G'的点和边都是图 G 的子集，则 G'为 G 的子图;

• 道路：从点 v 到点 u 的路径；

• 简单道路：没有重复边的道路；

• 回路：起点与终点相同的道路；

• 简单回路：没有重复边的回路；

• 连通：两顶点间有道路；

• 强连通：有向图 u→v 与 v→u 都有道路；

• 连通图：任意两顶点间都有道路（若有向图除去方向后连通，则称有向图连通）；

• 简单图：没有重复边和自环的图；

• 完全图：任意两顶点间有一条边到达的简单图（有向完全图与无向完全图）；

• 强连通（strongly connected）: 在有向图 G 中，如果两个顶点间至少存在一条路径，称两个顶点强连通（strongly connected）；

• 强连通图: 如果有向图 G 的每两个顶点都强连通，称 G 是一个强连通图；

• 强连通分量(strongly connected components): 非强连通图有向图的极大强连通子图，称为强连通分量(strongly connected components)。

求强连通分量就是我们今天要解决的问题，根据强连通分量定义，用双向遍历取交集的方法求强连通分量，时间复杂度为 O（$N^2$+M）. 而 Tarjan 或 Kosaraju 算法, 两者的时间复杂度都是 O（N+M）。

2.1. 算法简介

Tarjan 算法是基于对图深度优先搜索的算法，每个强连通分量为搜索树中的一棵子树。搜索时，把当前搜索树中未处理的节点加入一个堆栈，回溯时可以判断栈顶到栈中的节点是否为一个强连通分量。

• 定义:

o DFN(u)为节点 u 搜索的次序编号(时间戳);

o LOW(u)为 u 或 u 的子树能够追溯到的最早的栈中节点的次序号;

由定义可以得出，当 DFN(u)=LOW(u)时，以 u 为根的搜索子树上所有节点是一个强连通分量。

• 算法：

1. 当首次搜索到点 u 时 DFN[u]=LOW[u]=time;

2. 每当搜索到一个点，把该点压入栈顶;

3. 当 u 和 v 有边相连时:

1）如果 v 不在栈中（树枝边），DFS(v)，并且 LOW[u] = min{LOW(u),LOW(v)};

2）如果 v 在栈中（前向边/后向边），此时 LOW[u] = min{LOW[u],DFN[v]}

1. 当 DFN[u]=LOW[u]时，将它以及在它之上的元素弹出栈，此时，弹出栈的结点构成一个强连通分量;

2. 继续搜索，知道图被遍历完毕。

由于在这个过程中每个点只被访问一次，每条边也只被访问一次，所以 Tarjan 算法的时间复杂度是 O(n+m).

2.2. 算法伪代码

image

2.3. 举例演算

0.求下面有向图的强连通分量

image

1.从节点 0 开始 DFS:

• 代码(1)-(5): 得到访问链:0 -> 2 -> 4 -> 5, 把遍历到的 4 个节点{0, 2, 4, 5}加入栈中; 四个节点的 LOW[] 和 DFN[]值, 依次被 Index 标注成 1 到 4; 注: 这里也可以走另外一条路径: 0 -> 2 -> 3 -> 5;

• 代码(9)-(13): 节点 5 的后续边已经遍历完成, 退出节点 5 时, 发现 DFN[5] = LOW[5] = 4, 于是节点 5 出栈，{5}为一个强连通分量;

image

2.返回节点 4:

• 代码(6): LOW[4] = min(LOW[4], LOW[5]) = min(3, 4) = 3;

• 代码(9)-(13): 节点 4 的后续边已经遍历完成, 退出节点 4 时, DFN[4] = LOW[4] = 3; 退栈到节点 4 出栈，{4}为一个强连通分量;

image

3.返回节点 2:

• 代码(6): LOW[2] = min(LOW[2], LOW[4]) = min(2, 3) = 2;

image

4.从节点 2 继续搜索到节点 3:

• 代码(4)-(5): 继续遍历节点 2 的后续边, 找到节点 3;

• 代码(1)-(2): 把 3 加入堆栈, Index = 5, DFN[3] = LOW[3] = 5;

• 代码(3)-(8): 发现节点 3 向节点 0 有边(3 -> 0)，且节点 0 在栈中，所以 LOW[3] = min(LOW[3], DFN[0]) = min(5, 1) = 1。

• 代码(3)-(8): 发现节点 3 向节点 5 有边(3 -> 5), 但节点 5 已出栈;

image

5.返回节点 2;

• 代码(6): LOW[2] = min(LOW[2], LOW[3]) = min(2, 1) = 1;

image

6.返回节点 0;

• 代码(6): LOW[0] = min(LOW[0], LOW[2]) = min(1, 1) = 1;

image

7.从节点 0 继续搜索到节点 1;

• 代码(1)-(2): 把 1 加入堆栈, Index = 6, DFN[1] = LOW[1] = 6;

• 代码(3)-(8): 发现节点 1 向节点 3 有边(1 -> 3)，且节点 3 还在栈中，所以 LOW[1] = min(LOW[1], DFN[3]) = min(6, 5) = 5;

image

8.返回节点 0;

• 代码(9)-(13): 退出时发现 DFN[0] = LOW[0] = 1, 退栈到节点 0 出栈，组成一个连通分量{1, 3, 2, 0}。

image

• 最终, 所有节点和边都已经访问到, 得到所有连通分量: {5}, {4}, {1, 3, 2, 0}。

• 枚举边的时候, 与输入顺序相关, 可能计算顺序不同, 但过程中每个点只被访问一次，每条边也只被访问一次，所以总的结论一致.

2.4. Kosaraju 算法

Kosaraju 是基于对有向图及其逆图两次 DFS 的方法，其时间复杂度也是 O(N+M)。与 Trajan 算法相比，Kosaraju 算法可能会稍微更直观一些。但是 Tarjan 只用对原图进行一次 DFS，不用建立逆图，更简洁。

在实际的测试中，Tarjan 算法的运行效率也比 Kosaraju 算法高 30%左右。

3. Tarjan 算法实现

为了便于后期的扩展, 适用更为广泛的图运算。 这里算法的实现中，图的表示采用了 Google guava 库中的 common.graph, 你需要在 pom.xml 中加入 guava 的依赖包如下:

image

为了和举例中图的特征保持一致, 图结构采用 guava 里的 MutableGraph graph, Integer 的值表示结点的编号。 例如 graph.putEdge(0, 2); 表示增加一条有向边, 从结点 0 指向 结点 2, graph 会判断结点 0 和 2 是否存在结点中存在, 如不存在, 则会增加相应的结点。

大家可以根据自己的需要采用不同的图结构。

• 目前我们常用的图基础数据结构:

o JUNG: 2016.9.8 - 2.1.1. 据说作者正在打算采用 google 的 guava 重写这个工程;

o JGraphT: 2020.6.15 - 1.5.0. 这个是目前很活跃的一个图基础数据包, 里面也实现 Tarjan 算法, 后面有时间去看下具体的实现。 Maven 依赖的引用如下:

image

3.1. 算法代码

image

image

image

3.2. 验证代码

验证代码使用 junit 完成结果的验证。生成可变图 graph 里面的: incidentEdgeOrder(ElementOrder.stable()), 是为了保证关联边的读取时和输入的顺序一致, 以便得到和前面演算过程的一致性的结果.

image

4. 结论

• 计算机科学是一个综合性的学科;

• 基础科学的研究论文的重要性, 不仅在于其技术方面的贡献, 更重要的是它们提供一种概念上的见解或者一种研究范例；

• 基础科学对一个国家很重要；

• 计算机科学对一个国家很重要。

5. 参考

1. John E.Hoperoft 简介

2. 1986 年图灵奖 John E.Hoperoft 发言：COMPUTER SCIENCE: THE EMERGENCE OF A DISCIPLINE

3. Robert Endre Tarjan 简介

4. dblp - Robert Endre Tarjan

5. Depth-First Search and Linear Graph Algorithms

6. Guava Grpah
   

本文分享自华为云社区《史上最清晰的 Tarjan 算法详解》，原文作者：Uncle_Tom。

点击关注，第一时间了解华为云新鲜技术~