关于算法:史上最清晰的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）图灵奖的荣誉。

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)，在树的遍历过程中，扭转树的构造以进步树的搜寻效率。

他的次要荣誉：

• 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. 算法伪代码

2.3. 举例演算

0. 求上面有向图的强连通重量

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} 为一个强连通重量;

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} 为一个强连通重量;

3. 返回节点 2:

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

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 已出栈;

5. 返回节点 2;

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

6. 返回节点 0;

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

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;

8. 返回节点 0;

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

• 最终, 所有节点和边都曾经拜访到, 失去所有连通重量: {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 的依赖包如下:

为了和举例中图的特色保持一致, 图构造采纳 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 依赖的援用如下:

3.1. 算法代码

3.2. 验证代码

验证代码应用 junit 实现后果的验证。生成可变图 graph 外面的: incidentEdgeOrder(ElementOrder.stable()), 是为了保障关联边的读取时和输出的程序统一, 以便失去和后面演算过程的一致性的后果.

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。

点击关注，第一工夫理解华为云陈腐技术~