Tarjan(自己/合作)创造了哪些算法和数据结构?

答题大佬们能附上论文名最好了再问一句:求无向图的割顶和桥的算法是谁提出的?Bernard Chazelle(自己/合作)创造了哪些算法和数据结构?
关注者
149
被浏览
9,815

5 个回答

最小生成树线性时间随机化算法(A randomized linear-time algorithm to find minimum spanning trees)及其相关工作(其实时间复杂度不是严格线性的,只是期望为线性,别怪我标题党,论文名就是这样起的,逃

在介绍这个算法前,先介绍最小生成树的两个性质

  • 割性质(cut property):对于任意点集的子集X,一个点在X内,一个点在X外的所有边中,权值最小的那条边一定在最小生成树中
  • 环性质(cycle property):无向图中任意环上权值最大的边一定不在最小生成树中(注:谢谢知友 @后缀自动机·张 提出此处的表述错误,正确表述应该是权值大于环上所有边的边。原文的表述是任意重边(heavy edge)不在最小生成树中,重边定义如下)
Let G be a graph with weighted edges. We denote by w(x,y) the weight of edge {x, y}. If F is a forest in G, we denote by F(x,y) the path (if any) connecting x and y in F, and by w_F(x,y) the maximum weight of an edge on F(x,y) , with the convention that w_F(x,y) = \infty if x and y are not connected in F. We say an edge {x, y} is F-heavy if w(x,y)>w_F(x,y) , and F-light otherwise.

这两条性质都很好理解,以修公路为例,割性质说的是一个已经连接好的城市群要和外界相连,那必然是选择修最便宜的路了,环性质说的是,如果一堆城市可以构成回路,那拆掉最贵那条路,大家还是互联的。(我一直觉得学Prim和Kruskal算法之前应该先学这两条性质,理解了这两条性质,Prim和Kruskal的正确性一目了然)

Borůvka算法就是在这基础上提出的,每一趟Borůvka操作都把与每个点相连的权值最小的边加入最小生成树(把每个点当做子集,应用割性质),然后把每个连通分量缩成一个点,多重边(multiple edge)保留最小的那条,构建一个新图,再对新图做Borůvka操作,直到变成孤立的点。你可以把这个算法过程理解为一个函数反复apply直到收敛的过程,即达到不动点f(x)=x,也可以把它理解为一个递归函数,每一次调用都是先算出一部分边,然后递归求压缩图的最小生成树,最后返回一个最小生成树。

这才只用上割性质啊,那环性质用来做什么的呢?

割性质断言的是某些边一定在最小生成树中,我们用这个断言来构建最小生成树,而环性质断言的是某些边一定不在最小生成树中,既然如此,如果我们能找到这些边,把它从原图中删除,那么原图在进行递归Borůvka操作时,规模就变小了。

于是,随机化的算法是这样做的,先进行两次Borůvka操作,然后在缩点后的图中以一定的规则选择一个子图,计算这个子图的最小生成树,然后根据这个结果,找到环性质断言的那些边(文中称为重边(heavy edge),顾名思义,太重,不能出现在最小生成树中),从原图中删除,再对原图进行递归调用求解最小生成树。然后一堆balabala概率论分析,balabala引理,最后证明这个的期望复杂度是线性的。

好了,说了这么多,哪些跟Tarjan有关系呢?

  • 最小生成树的割性质(cut property)和环性质(cycle property)对应Tarjan提出的red ruleblue rule
  • 上述最小生成树的随机化算法是DAVID R. KARGER,PHILIP N. KLEIN,ROBERT E. TARJAN三人提出的
  • 随机化算法中有一步,通过子图的最小生成树找到重边(heavy edge),这一步用到了一个线性时间的验证给定生成树是否是最小生成树的算法(下称最小生成树线性验证算法),那个算法的论文作者中也有Tarjan。
  • 最小生成树随机化算法和最小生成树线性验证算法的论文中多次引用Tarjan在80年代关于图论的工作(简单搜了一下,两篇论文中引用了8篇Tarjan的论文或著作)
  • ……


就个人印象来说,Tarjan是一个兼具天才的直觉与实干的精神的一个计算机科学家,既仰望星空,又脚踏实地。既提出一些大开脑洞的设想,又认真从脚下做起,认真地为众人铺路。这种心境值得所有做研究的人学习。

最后,看到这个题目有NOI/ACM标签,我瞬间就出戏了。我猜题主是在OI/ACM中学了好几个Tarjan算法,于是对Tarjan心生敬佩之情,然后想了解一下他提出了哪些算法,想一网打尽,学到屠龙之术。我当初做这个算法的Presentation的时候也是这样想的,哇!线性时间的最小生成树!学会了在OI/ACM里岂不是吊打Prim/Kruskal!看完论文之后我才傻眼了,尼玛!这么复杂的过程,写完都比完了!



丢完参考文献就跑

  1. Klein P N, Tarjan R E. A Randomized Linear-Time Algorithm for Finding Minimum Spanning Trees[M]. Brown University, 1993.
  2. Dixon B, Rauch M, Tarjan R E. Verification and Sensitivity Analysis Of Minimum Spanning Trees In Linear Time[C]// SIAM J. COMPUT. 1992:1184--1192.

再丢一点相关资料吧

  1. 某大学的slides cs.technion.ac.il/~iddd
  2. 随机化最小生成树算法gayhub某老哥的实现,1k多行代码 Robert-Emerson/6161_final

显然,要全部写出来实在是太多了。。就说几个有名的吧。

按照相关论文最早在会议或期刊上发表的时间排序。

  • Tarjan's SCCs algorithm (Tarjan强连通分量算法). Tarjan, Robert Endre (1971). "Depth-first search and linear graph algorithms".
  • Tarjan's BCCs algorithm (Tarjan双连通分量算法). Hopcroft, John Edward; Tarjan, R. E. (1973). "Algorithm 447: efficient algorithms for graph manipulation".
  • 线性时间找出图的桥. Tarjan, R. E. (1974). "A Note on Finding the Bridges of a Graph".
  • Link/cut tree. Sleator, Daniel Dominic; Tarjan, R. E. (1981). "A Data Structure for Dynamic Trees".
  • Fibonacci heap (Fibonacci堆). Fredman, Michael Lawrence; Tarjan, R. E. (1984). "Fibonacci heaps and their uses in improved network optimization algorithms".
  • Splay tree (伸展树). Sleator, D. D.; Tarjan, R. E. (1985). "Self-Adjusting Binary Search Trees".
  • Persistent data structure (持久化数据结构). Driscoll, James R.; Sarnak, Neil; Sleator, D. D.; Tarjan, R. E. (1986). "Making Data Structures Persistent".
  • Skew heap (斜堆). Sleator, D. D.; Tarjan, R. E. (1986). "Self-Adjusting Heaps".
  • Pairing heap (配对堆). Fredman, M. L.; Sedgewick, Robert; Sleator, D. D.; Tarjan, R. E. (1986). "The Pairing Heap: A New Form of Self-Adjusting Heap".
  • Self-adjusting top trees. Tarjan, R. E.; Werneck, Renato Fonseca Furquim (2005). "Self-Adjusting Top Trees".

这里收录了Tarjan所有公开发表的论文,有兴趣的话可以看看。

注意 Tarjan's off-line LCA algorithm (Tarjan离线LCA算法) 并不是Tarjan的。Aho, Alfred Vaino; Hopcroft, J. E.; Ullman, Jeffrey David (1973). "On Finding Lowest Common Ancestors in Trees".