有同學(xué)在學(xué)習(xí)圖論算法的時(shí)候，發(fā)現(xiàn)這里有個(gè) Tarjan 算法，那里有個(gè) Tarjan 算法，而似乎 Tarjan 算法解決的問(wèn)題并不一樣，于是非常迷惑：Tarjan 算法到底是指什么？

這是一個(gè)很好的問(wèn)題。Tarjan 是計(jì)算機(jī)領(lǐng)域的大牛，發(fā)明了很多現(xiàn)在大家耳熟能詳?shù)乃惴ɑ蛘邤?shù)據(jù)結(jié)構(gòu)，所以有同學(xué)會(huì)覺(jué)得冠他名字的算法有些多。

但如果我們仔細(xì)梳理一下，其實(shí)并不復(fù)雜。

在這篇文章中，我會(huì)帶領(lǐng)大家梳理一下 Tarjan 發(fā)明的算法都有哪些，整體脈絡(luò)是怎樣的。

注意：在這篇文章中，我不會(huì)具體講解某個(gè)算法的原理。但是，我會(huì)給出很多具體的關(guān)鍵字，并且標(biāo)紅。如果大家對(duì)某個(gè)算法想深入了解，可以以此為引，在互聯(lián)網(wǎng)上搜索學(xué)習(xí)。

我相信，互聯(lián)網(wǎng)上關(guān)于某個(gè)具體算法的資料是非常多的，反而是這樣按照某個(gè)脈絡(luò)做總結(jié)的文章很少。

首先，Tarjan 是一名美國(guó)的計(jì)算機(jī)科學(xué)家和數(shù)學(xué)家，全名 Robert Endre Tarjan。

先來(lái)一個(gè) Tarjan 大神的名言鎮(zhèn)樓：

一般提起 Tarjan 算法，通常是指 Tarjan 發(fā)明的求解有向圖的強(qiáng)聯(lián)通分量算法，全稱(chēng)是Tarjan’s Strongly Connected Components Algorithm.

為什么這么叫？因?yàn)榍蠼庥邢驁D的強(qiáng)聯(lián)通分量還有一個(gè)著名算法：Kosaraju 算法。Kosaraju 算法也是以他的發(fā)明者的名字命名的。

我在算法比賽中，或者需要求解 SCC（強(qiáng)連通分量的縮寫(xiě)：Strongly Connected Components） 問(wèn)題的時(shí)候，喜歡寫(xiě) Kosaraju 算法。因?yàn)?Kosaraju 算法的實(shí)現(xiàn)非常簡(jiǎn)單，復(fù)雜度和 Tarjan 算法是一樣的，都是 O(V + E) 的。

但實(shí)際上，Kosaraju 算法需要遍歷兩次圖，而 Tarjan 算法只需要遍歷一次圖。所以，Tarjan 算法的性能更高，一般可以高 30% - 40% 左右。

而 Tarjan 算法之所以有名，關(guān)鍵在于使用 Tarjan 算法的思想，不僅僅可以求解 SCC 問(wèn)題，還可以求無(wú)向圖中的橋或者割點(diǎn)。

這就是為什么，很多同學(xué)看到 Tarjan 算法，做的事情不一樣，但都叫 Tarjan 算法的原因。我們可以把 Tarjan 算法理解成是一種思想，基于這種思想，可以求解橋，割點(diǎn)，和 SCC 問(wèn)題。

所謂的 Tarjan 算法思想，就是在遍歷整個(gè)圖的過(guò)程中，對(duì)每一個(gè)遍歷的節(jié)點(diǎn)記錄一個(gè)時(shí)間戳，通常被稱(chēng)為是 DFN；同時(shí)，記錄通過(guò)這個(gè)節(jié)點(diǎn)，不經(jīng)過(guò)父親節(jié)點(diǎn)，最早能回到的時(shí)間戳，通常被稱(chēng)為是 LOW。通過(guò)這些信息，就能判斷一個(gè)圖的橋，割點(diǎn)，和強(qiáng)連通分量。

然而，Tarjan 的貢獻(xiàn)遠(yuǎn)不止于此。以Tarjan命名的另外一個(gè)非常著名的算法，叫Tarjan‘s Off-line Least Common Ancestors Algorithm。

這個(gè)算法本質(zhì)是借助并查集，求解 LCA（最近公共祖先的縮寫(xiě)：Least Common Ancestors）問(wèn)題。

實(shí)際上，離線的 LCA 問(wèn)題，是計(jì)算機(jī)科學(xué)領(lǐng)域非常著名的問(wèn)題，深究下去，和Binary Lifting，RMQ等非常著名的算法思想都有聯(lián)系。

說(shuō)到并查集，Tarjan 也和這種數(shù)據(jù)結(jié)構(gòu)有不解之緣。并查集雖然不是 Tarjan 發(fā)明的，但是并查集的復(fù)雜度是 Tarjan 首先分析清楚的：也就是Ackerman 函數(shù)的反函數(shù)。

如果對(duì)此感興趣的同學(xué)，可以翻看《算法導(dǎo)論》，《算法導(dǎo)論》對(duì)這部分內(nèi)容介紹得很清楚。

實(shí)際上，這也是《算法導(dǎo)論》這本教材的意義：稍微深入一些的算法分析問(wèn)題，一般的算法教材都不會(huì)涉及。而《算法導(dǎo)論》所覆蓋的深度和廣度，比大多數(shù)教材都高太多。

當(dāng)然，這也是《算法導(dǎo)論》不適合入門(mén)的原因。

說(shuō)到數(shù)據(jù)結(jié)構(gòu)，Tarjan 確實(shí)發(fā)明過(guò)數(shù)據(jù)結(jié)構(gòu)。最有名的兩個(gè)，一個(gè)是斐波那契堆，一個(gè)是Splay 樹(shù)。

Splay 樹(shù)雖然不保證一定平衡，但各個(gè)操作的均攤復(fù)雜度是 O(logn) 級(jí)別的。

Splay 樹(shù)最大的優(yōu)勢(shì)是實(shí)現(xiàn)簡(jiǎn)單，比紅黑樹(shù)簡(jiǎn)單不知道多少倍。所以，如果我們需要調(diào)用更加底層的樹(shù)操作，需要自己實(shí)現(xiàn)一個(gè)自平衡的二分搜索樹(shù)時(shí)，通常 Splay 樹(shù)是首選。

也正因?yàn)槿绱?，很多搞?jìng)賽的同學(xué)，都是能手寫(xiě) Splay 樹(shù)的。

Tarjan 還是非常著名的算法：BFPRT的作者之一。其實(shí) BFPRT 這個(gè)算法的名字，是其五個(gè)作者首字母的縮寫(xiě)。其中的 T，就是 Tarjan。

BFPRT 這個(gè)名字聽(tīng)起來(lái)非常拗口，同時(shí)也難記，但是它的另一個(gè)名字就很簡(jiǎn)單直接了，就是Median of Medians。

這個(gè)算法整體并不難理解，是快排思想的一種更穩(wěn)定的優(yōu)化，每次近乎可以保證選取所處理的數(shù)組的中位數(shù)作為標(biāo)定點(diǎn)（pivot），使得快速排序的最差時(shí)間復(fù)雜度真真正正達(dá)到了 O(nlogn)。

值得一提的是，BFPRT 算法的這五位作者，都是計(jì)算機(jī)科學(xué)領(lǐng)域的大牛。他們分別是：

B是 Blum，全名 Manuel Blum，他因?yàn)閺?fù)雜度理論方面的貢獻(xiàn)，以及密碼學(xué)的應(yīng)用，獲得了 1995 年的圖靈獎(jiǎng)；

F是 Floyd，全名 Robert W. Floyd，相信大家都很熟悉。大家在算法課本上一定會(huì)學(xué)到的所有點(diǎn)對(duì)的最短路徑算法，就是他和 Warshall 一起提出的，即Floyd–Warshall 算法。同時(shí)，F(xiàn)loyed 還提出了非常著名的Floyed 環(huán)檢測(cè)算法。他獲得了 1978 年的圖靈獎(jiǎng)；

P是 Pratt，全名 Vaughan Pratt，是斯坦福的教授；

R是 Rivest，全名 Ron Rivest。他是 MIT 的教授，專(zhuān)攻密碼學(xué)。我們現(xiàn)在所經(jīng)常使用的MD5 算法，他就是作者之一；

最后的T，就是這篇文章的主角：Tarjan，全名 Robert Endre Tarjan。

在圖論領(lǐng)域，Tarjan 還改進(jìn)了一個(gè)非常著名的算法：最小樹(shù)形圖。最小樹(shù)形圖這個(gè)名字聽(tīng)起來(lái)很復(fù)雜，但其實(shí)這個(gè)概念很簡(jiǎn)單：就是有向圖的最小生成樹(shù)。

解決最小樹(shù)形圖問(wèn)題，有一個(gè)非常樸素的算法，叫朱劉算法。聽(tīng)這個(gè)名字大家也知道，這是兩位華人科學(xué)家首先提出來(lái)的算法，在論文記載中，分別是 Y.J. Chu 和 T.H. Liu 在 1965 年提出來(lái)的。朱劉算法的時(shí)間復(fù)雜度是 O(VE) 的。

后來(lái)，Tarjan 改進(jìn)了這個(gè)算法，可以使用 O(ElogV) 的時(shí)間做預(yù)處理，之后使用 O(V) 的時(shí)間，求解圖中以任意頂點(diǎn)為根的最小樹(shù)形圖

Tarjan 還發(fā)明了一種平面圖的檢測(cè)算法，首次在線性時(shí)間解決了平面圖檢測(cè)問(wèn)題（Planarity-Testing）。因?yàn)槠矫鎴D檢測(cè)離大多數(shù)同學(xué)的工作比較遠(yuǎn)，所以可能很少有同學(xué)了解這個(gè)算法。

Tarjan 的平面圖檢測(cè)算法還有一個(gè)合作者：John Hopcroft。他們二人因?yàn)檫@個(gè)算法，以及在算法和數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)領(lǐng)域?qū)τ?jì)算機(jī)科學(xué)的貢獻(xiàn)，獲得了 1986 年的圖靈獎(jiǎng)。

Tarjan 的碩士和博士是在斯坦福大學(xué)讀的。他的導(dǎo)師有兩個(gè)。一個(gè)就是大名鼎鼎的 Floyd，上文介紹 BFPRT 算法的時(shí)候介紹了。在這里給一個(gè)年輕的時(shí)候，F(xiàn)loyd 風(fēng)流倜儻的帥照：

Tarjan 的另一名導(dǎo)師，則是計(jì)算機(jī)科學(xué)領(lǐng)域的神級(jí)人物：Donald Knuth。他可以說(shuō)是計(jì)算復(fù)雜領(lǐng)域的創(chuàng)始人。

Donald Knuth 的經(jīng)歷和貢獻(xiàn)，可以寫(xiě)一本書(shū)了。有時(shí)間，我會(huì)再寫(xiě)一篇文章介紹他?，F(xiàn)在，很多人了解他，都是因?yàn)樗纳褡鳎篢AOCP，即The Art of Computer Programming，被中文翻譯成《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》。這套書(shū)被評(píng)為至今計(jì)算機(jī)科學(xué)史上最重要的神作，但其實(shí)還沒(méi)有寫(xiě)完。

不過(guò) Donald Knuth 對(duì)計(jì)算機(jī)科學(xué)領(lǐng)域的貢獻(xiàn)，遠(yuǎn)不止一套書(shū)這么簡(jiǎn)單。要聊 Donald Knuth 的話，能聊的就太多。這篇文章我們收一收，說(shuō)回 Tarjan。

Tarjan 現(xiàn)在還在世，今年已經(jīng) 72 歲了。根據(jù)維基百科，現(xiàn)在 Tarjan 在普林斯頓任教。

實(shí)際上，在計(jì)算機(jī)科學(xué)領(lǐng)域，很多在教科書(shū)中出現(xiàn)的人物，都還在世；很多教科書(shū)級(jí)別的算法，概念，理論，其實(shí)距離提出，也不過(guò)是幾十年的時(shí)間。

這足以可見(jiàn)：計(jì)算機(jī)是多么年輕的一個(gè)學(xué)科。

也正是因?yàn)檫@個(gè)原因，在計(jì)算機(jī)科學(xué)領(lǐng)域中，還有大量的沒(méi)有被完全解決的問(wèn)題。

計(jì)算機(jī)科學(xué)領(lǐng)域其實(shí)還大有可為。

責(zé)任編輯：xj

原文標(biāo)題：Tarjan 這個(gè)算法大神

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。