有同學(xué)在學(xué)習(xí)圖論算法的時候,發(fā)現(xiàn)這里有個 Tarjan 算法,那里有個 Tarjan 算法,而似乎 Tarjan 算法解決的問題并不一樣,于是非常迷惑:Tarjan 算法到底是指什么?
這是一個很好的問題。Tarjan 是計算機領(lǐng)域的大牛,發(fā)明了很多現(xiàn)在大家耳熟能詳?shù)乃惴ɑ蛘邤?shù)據(jù)結(jié)構(gòu),所以有同學(xué)會覺得冠他名字的算法有些多。
但如果我們仔細(xì)梳理一下,其實并不復(fù)雜。
在這篇文章中,我會帶領(lǐng)大家梳理一下 Tarjan 發(fā)明的算法都有哪些,整體脈絡(luò)是怎樣的。
注意:在這篇文章中,我不會具體講解某個算法的原理。但是,我會給出很多具體的關(guān)鍵字,并且標(biāo)紅。如果大家對某個算法想深入了解,可以以此為引,在互聯(lián)網(wǎng)上搜索學(xué)習(xí)。
我相信,互聯(lián)網(wǎng)上關(guān)于某個具體算法的資料是非常多的,反而是這樣按照某個脈絡(luò)做總結(jié)的文章很少。
首先,Tarjan 是一名美國的計算機科學(xué)家和數(shù)學(xué)家,全名 Robert Endre Tarjan。
先來一個 Tarjan 大神的名言鎮(zhèn)樓:
一般提起 Tarjan 算法,通常是指 Tarjan 發(fā)明的求解有向圖的強聯(lián)通分量算法,全稱是Tarjan’s Strongly Connected Components Algorithm.
為什么這么叫?因為求解有向圖的強聯(lián)通分量還有一個著名算法:Kosaraju 算法。Kosaraju 算法也是以他的發(fā)明者的名字命名的。
我在算法比賽中,或者需要求解 SCC(強連通分量的縮寫:Strongly Connected Components) 問題的時候,喜歡寫 Kosaraju 算法。因為 Kosaraju 算法的實現(xiàn)非常簡單,復(fù)雜度和 Tarjan 算法是一樣的,都是 O(V + E) 的。
但實際上,Kosaraju 算法需要遍歷兩次圖,而 Tarjan 算法只需要遍歷一次圖。所以,Tarjan 算法的性能更高,一般可以高 30% - 40% 左右。
而 Tarjan 算法之所以有名,關(guān)鍵在于使用 Tarjan 算法的思想,不僅僅可以求解 SCC 問題,還可以求無向圖中的橋或者割點。
這就是為什么,很多同學(xué)看到 Tarjan 算法,做的事情不一樣,但都叫 Tarjan 算法的原因。我們可以把 Tarjan 算法理解成是一種思想,基于這種思想,可以求解橋,割點,和 SCC 問題。
所謂的 Tarjan 算法思想,就是在遍歷整個圖的過程中,對每一個遍歷的節(jié)點記錄一個時間戳,通常被稱為是 DFN;同時,記錄通過這個節(jié)點,不經(jīng)過父親節(jié)點,最早能回到的時間戳,通常被稱為是 LOW。通過這些信息,就能判斷一個圖的橋,割點,和強連通分量。
然而,Tarjan 的貢獻(xiàn)遠(yuǎn)不止于此。以Tarjan命名的另外一個非常著名的算法,叫Tarjan‘s Off-line Least Common Ancestors Algorithm。
這個算法本質(zhì)是借助并查集,求解 LCA(最近公共祖先的縮寫:Least Common Ancestors)問題。
實際上,離線的 LCA 問題,是計算機科學(xué)領(lǐng)域非常著名的問題,深究下去,和Binary Lifting,RMQ等非常著名的算法思想都有聯(lián)系。
說到并查集,Tarjan 也和這種數(shù)據(jù)結(jié)構(gòu)有不解之緣。并查集雖然不是 Tarjan 發(fā)明的,但是并查集的復(fù)雜度是 Tarjan 首先分析清楚的:也就是Ackerman 函數(shù)的反函數(shù)。
如果對此感興趣的同學(xué),可以翻看《算法導(dǎo)論》,《算法導(dǎo)論》對這部分內(nèi)容介紹得很清楚。
實際上,這也是《算法導(dǎo)論》這本教材的意義:稍微深入一些的算法分析問題,一般的算法教材都不會涉及。而《算法導(dǎo)論》所覆蓋的深度和廣度,比大多數(shù)教材都高太多。
當(dāng)然,這也是《算法導(dǎo)論》不適合入門的原因。
說到數(shù)據(jù)結(jié)構(gòu),Tarjan 確實發(fā)明過數(shù)據(jù)結(jié)構(gòu)。最有名的兩個,一個是斐波那契堆,一個是Splay 樹。
Splay 樹雖然不保證一定平衡,但各個操作的均攤復(fù)雜度是 O(logn) 級別的。
Splay 樹最大的優(yōu)勢是實現(xiàn)簡單,比紅黑樹簡單不知道多少倍。所以,如果我們需要調(diào)用更加底層的樹操作,需要自己實現(xiàn)一個自平衡的二分搜索樹時,通常 Splay 樹是首選。
也正因為如此,很多搞競賽的同學(xué),都是能手寫 Splay 樹的。
Tarjan 還是非常著名的算法:BFPRT的作者之一。其實 BFPRT 這個算法的名字,是其五個作者首字母的縮寫。其中的 T,就是 Tarjan。
BFPRT 這個名字聽起來非常拗口,同時也難記,但是它的另一個名字就很簡單直接了,就是Median of Medians。
這個算法整體并不難理解,是快排思想的一種更穩(wěn)定的優(yōu)化,每次近乎可以保證選取所處理的數(shù)組的中位數(shù)作為標(biāo)定點(pivot),使得快速排序的最差時間復(fù)雜度真真正正達(dá)到了 O(nlogn)。
值得一提的是,BFPRT 算法的這五位作者,都是計算機科學(xué)領(lǐng)域的大牛。他們分別是:
B是 Blum,全名 Manuel Blum,他因為復(fù)雜度理論方面的貢獻(xiàn),以及密碼學(xué)的應(yīng)用,獲得了 1995 年的圖靈獎;
F是 Floyd,全名 Robert W. Floyd,相信大家都很熟悉。大家在算法課本上一定會學(xué)到的所有點對的最短路徑算法,就是他和 Warshall 一起提出的,即Floyd–Warshall 算法。同時,F(xiàn)loyed 還提出了非常著名的Floyed 環(huán)檢測算法。他獲得了 1978 年的圖靈獎;
P是 Pratt,全名 Vaughan Pratt,是斯坦福的教授;
R是 Rivest,全名 Ron Rivest。他是 MIT 的教授,專攻密碼學(xué)。我們現(xiàn)在所經(jīng)常使用的MD5 算法,他就是作者之一;
最后的T,就是這篇文章的主角:Tarjan,全名 Robert Endre Tarjan。
在圖論領(lǐng)域,Tarjan 還改進(jìn)了一個非常著名的算法:最小樹形圖。最小樹形圖這個名字聽起來很復(fù)雜,但其實這個概念很簡單:就是有向圖的最小生成樹。
解決最小樹形圖問題,有一個非常樸素的算法,叫朱劉算法。聽這個名字大家也知道,這是兩位華人科學(xué)家首先提出來的算法,在論文記載中,分別是 Y.J. Chu 和 T.H. Liu 在 1965 年提出來的。朱劉算法的時間復(fù)雜度是 O(VE) 的。
后來,Tarjan 改進(jìn)了這個算法,可以使用 O(ElogV) 的時間做預(yù)處理,之后使用 O(V) 的時間,求解圖中以任意頂點為根的最小樹形圖
Tarjan 還發(fā)明了一種平面圖的檢測算法,首次在線性時間解決了平面圖檢測問題(Planarity-Testing)。因為平面圖檢測離大多數(shù)同學(xué)的工作比較遠(yuǎn),所以可能很少有同學(xué)了解這個算法。
Tarjan 的平面圖檢測算法還有一個合作者:John Hopcroft。他們二人因為這個算法,以及在算法和數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)領(lǐng)域?qū)τ嬎銠C科學(xué)的貢獻(xiàn),獲得了 1986 年的圖靈獎。
Tarjan 的碩士和博士是在斯坦福大學(xué)讀的。他的導(dǎo)師有兩個。一個就是大名鼎鼎的 Floyd,上文介紹 BFPRT 算法的時候介紹了。在這里給一個年輕的時候,F(xiàn)loyd 風(fēng)流倜儻的帥照:
Tarjan 的另一名導(dǎo)師,則是計算機科學(xué)領(lǐng)域的神級人物:Donald Knuth。他可以說是計算復(fù)雜領(lǐng)域的創(chuàng)始人。
Donald Knuth 的經(jīng)歷和貢獻(xiàn),可以寫一本書了。有時間,我會再寫一篇文章介紹他。現(xiàn)在,很多人了解他,都是因為他的神作:TAOCP,即The Art of Computer Programming,被中文翻譯成《計算機程序設(shè)計藝術(shù)》。這套書被評為至今計算機科學(xué)史上最重要的神作,但其實還沒有寫完。
不過 Donald Knuth 對計算機科學(xué)領(lǐng)域的貢獻(xiàn),遠(yuǎn)不止一套書這么簡單。要聊 Donald Knuth 的話,能聊的就太多。這篇文章我們收一收,說回 Tarjan。
Tarjan 現(xiàn)在還在世,今年已經(jīng) 72 歲了。根據(jù)維基百科,現(xiàn)在 Tarjan 在普林斯頓任教。
實際上,在計算機科學(xué)領(lǐng)域,很多在教科書中出現(xiàn)的人物,都還在世;很多教科書級別的算法,概念,理論,其實距離提出,也不過是幾十年的時間。
這足以可見:計算機是多么年輕的一個學(xué)科。
也正是因為這個原因,在計算機科學(xué)領(lǐng)域中,還有大量的沒有被完全解決的問題。
計算機科學(xué)領(lǐng)域其實還大有可為。
責(zé)任編輯:xj
原文標(biāo)題:Tarjan 這個算法大神
文章出處:【微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
-
算法
+關(guān)注
關(guān)注
23文章
4629瀏覽量
93193 -
計算機
+關(guān)注
關(guān)注
19文章
7534瀏覽量
88451
原文標(biāo)題:Tarjan 這個算法大神
文章出處:【微信號:TheAlgorithm,微信公眾號:算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注!文章轉(zhuǎn)載請注明出處。
發(fā)布評論請先 登錄
相關(guān)推薦
評論