计算机人物 | Tarjan 24岁写下的几个算法，今天还在每个信奥孩子的题单里？

Tarjan算法，信奥圈的孩子肯定很熟啊

4月30日，是Robert Tarjan的78岁生日。目前他还在普林斯顿带博士生。

1986年他和John Hopcroft共享图灵奖，到今年正好40年。

如果你家孩子在打信奥，"Tarjan"这个名字一定见过。

求强连通分量的Tarjan算法、并查集路径压缩、Splay树、Fibonacci堆、Link-cut tree。这些散落在算法竞赛教材里的名字，作者都是同一个人。

24岁博士毕业那年

1972年，Tarjan在斯坦福拿到博士学位。导师是Robert Floyd（Floyd-Warshall算法的那个Floyd），Donald Knuth也参与了指导。

同年他写了一篇叫《Depth-First Search and Linear Graph Algorithms》的论文，用深度优先搜索把几个经典的图论问题做到了线性时间。今天信奥课程里的Tarjan强连通分量算法，就出自这里。

80年代：动态树、Splay树、Fibonacci堆

Tarjan和Daniel Sleator（后来的CMU教授）合作做了两件事：

1983年的动态树（Link-cut tree），能在树上动态加边、删边、查询路径信息。

1985年的Splay树，一种"自我调整"的二叉搜索树。每次访问把节点旋转到根，看似简单，摊下来的效率不输任何一种平衡树。

1987年，Tarjan又和Michael Fredman做出了Fibonacci堆。让Dijkstra算法跑得更快。今天每本图算法教材讲完Dijkstra之后，下一节几乎都是它。

学术界，工业界，都不耽误

1985年起在普林斯顿任教。同时一直在工业界：贝尔实验室、NEC研究院、Intertrust、HP Labs、微软研究院都做过。

很多人以为做算法的人都关在象牙塔里。Tarjan不是。从普林斯顿的黑板到湾区的服务器，是同一套东西。

一家人，研究的都是"思考"

Tarjan的父亲在匈牙利长大，是儿童精神科医生，专门研究智力障碍。

弟弟James Tarjan，是国际象棋特级大师。

爸爸研究"人为什么学得慢"，弟弟一辈子在棋盘上找最优一步，Tarjan自己写算法在搜索空间里找最优解。一家三个人，研究的都是"思考"的不同侧面。