0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

算法大神Tarjan

算法與數(shù)據(jù)結(jié)構(gòu) ? 來源:算法與數(shù)據(jù)結(jié)構(gòu) ? 作者:算法與數(shù)據(jù)結(jié)構(gòu) ? 2021-01-04 14:23 ? 次閱讀

有同學(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。通過這些信息,就能判斷一個圖的橋,割點,和強連通分量。

2ae9bf46-4423-11eb-8b86-12bb97331649.png

然而,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)系。

2b0ed164-4423-11eb-8b86-12bb97331649.png

說到并查集,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)載請注明出處。

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(liá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)載請注明出處。

收藏 0人收藏

    評論

    相關(guān)推薦

    算法加速的概念、意義、流程和應(yīng)用

    本文介紹算法加速的概念、意義、流程和應(yīng)用 一、什么是算法加速 面向“最耗時”的部分做專用化處理: 在軟件運行時,總有一些特定算法會消耗大量 CPU 資源,比如加密解密、圖像處理或神經(jīng)網(wǎng)絡(luò)推理。這類
    的頭像 發(fā)表于 01-15 09:34 ?104次閱讀

    【「從算法到電路—數(shù)字芯片算法的電路實現(xiàn)」閱讀體驗】+內(nèi)容簡介

    內(nèi)容簡介這是一本深入解讀基礎(chǔ)算法及其電路設(shè)計,以打通算法研發(fā)到數(shù)字IC設(shè)計的實現(xiàn)屏障,以及指導(dǎo)芯片設(shè)計工程師從底層掌握復(fù)雜電路設(shè)計與優(yōu)化方法為目標(biāo)的專業(yè)技術(shù)書。任何芯片(如WiFi芯片、5G芯片
    發(fā)表于 11-21 17:14

    【「從算法到電路—數(shù)字芯片算法的電路實現(xiàn)」閱讀體驗】+介紹基礎(chǔ)硬件算法模塊

    作為嵌入式開發(fā)者往往比較關(guān)注硬件和軟件的協(xié)調(diào)。本書介紹了除法器,信號發(fā)生器,濾波器,分頻器等基本算法的電路實現(xiàn),雖然都是基礎(chǔ)內(nèi)容,但是也是最常用到的基本模塊。 隨著逆全球化趨勢的出現(xiàn),過去的研發(fā)
    發(fā)表于 11-21 17:05

    【「從算法到電路—數(shù)字芯片算法的電路實現(xiàn)」閱讀體驗】+一本介紹基礎(chǔ)硬件算法模塊實現(xiàn)的好書

    作為嵌入式開發(fā)者往往比較關(guān)注硬件和軟件的協(xié)調(diào)。本書介紹了除法器,信號發(fā)生器,濾波器,分頻器等基本算法的電路實現(xiàn),雖然都是基礎(chǔ)內(nèi)容,但是也是最常用到的基本模塊,本書的內(nèi)容比較對本人胃口。 我們先來
    發(fā)表于 11-20 13:42

    Pure path studio內(nèi)能否自己創(chuàng)建一個component,來實現(xiàn)特定的算法,例如LMS算法?

    TLV320AIC3254EVM-K評估模塊, Pure path studio軟件開發(fā)環(huán)境。 問題:1.Pure path studio 內(nèi)能否自己創(chuàng)建一個component,來實現(xiàn)特定的算法
    發(fā)表于 11-01 08:25

    請問GDE中的NR算法反應(yīng)慢怎么解決?

    我在使用NR(NoiseReduction)算法時發(fā)現(xiàn)算法起作用的時間太長,輸入1K正弦波測試,大約是在輸入40秒以后出現(xiàn)下圖轉(zhuǎn)變 再過段時間又變成下圖的樣子。 但是播放器重新開始的短暫停止也
    發(fā)表于 10-29 07:42

    壓縮算法的類型和應(yīng)用

    壓縮算法是一種通過減少數(shù)據(jù)量來節(jié)省存儲空間或傳輸數(shù)據(jù)的技術(shù)。壓縮算法可以分為兩種類型:有損壓縮和無損壓縮。
    的頭像 發(fā)表于 10-21 13:50 ?339次閱讀

    名單公布!【書籍評測活動NO.46】從算法到電路 | 數(shù)字芯片算法的電路實現(xiàn)

    :elecfans123)領(lǐng)取書籍進(jìn)行評測,如在5個工作日內(nèi)未聯(lián)系,視為放棄本次試用評測資格! 《從算法到電路——數(shù)字芯片算法的電路實現(xiàn)》 是一本深入解讀基礎(chǔ)算法及其電路設(shè)計,以打通算法
    發(fā)表于 10-09 13:43

    常用的ADC濾波算法有哪些

    ADC(模數(shù)轉(zhuǎn)換器)濾波算法在信號處理中起著至關(guān)重要的作用,它們能夠幫助我們提取出有用的信號,同時濾除噪聲和干擾。以下是常用的ADC濾波算法詳解,這些算法各具特色,適用于不同的應(yīng)用場景。
    的頭像 發(fā)表于 10-08 14:35 ?480次閱讀

    充電也要算法?儲能充電芯片中的算法處理器

    電子發(fā)燒友網(wǎng)報道(文/黃山明)充電算法處理器是一種專門設(shè)計用于執(zhí)行充電算法的微處理器或ASIC,這些算法可以優(yōu)化電池的充電過程,提高充電效率,延長電池壽命,并確保充電安全。這種處理器通常集成在BMS
    的頭像 發(fā)表于 07-30 00:07 ?3781次閱讀

    機器學(xué)習(xí)算法原理詳解

    機器學(xué)習(xí)作為人工智能的一個重要分支,其目標(biāo)是通過讓計算機自動從數(shù)據(jù)中學(xué)習(xí)并改進(jìn)其性能,而無需進(jìn)行明確的編程。本文將深入解讀幾種常見的機器學(xué)習(xí)算法原理,包括線性回歸、邏輯回歸、支持向量機(SVM)、決策樹和K近鄰(KNN)算法,探討它們的理論基礎(chǔ)、
    的頭像 發(fā)表于 07-02 11:25 ?1286次閱讀

    BLDC電機控制算法詳解

    算法。本文將詳細(xì)介紹BLDC電機的控制算法,包括電速算法、電流環(huán)控制算法、磁場導(dǎo)向控制算法等,并探討其原理、特點和應(yīng)用。
    的頭像 發(fā)表于 06-14 10:49 ?1183次閱讀

    運動控制算法有哪些

    運動控制算法是機器人學(xué)和自動化領(lǐng)域中的核心技術(shù)之一,它們負(fù)責(zé)規(guī)劃和執(zhí)行機器人或自動化設(shè)備的精確運動。以下是一些常見的運動控制算法,以及它們的基本原理和應(yīng)用場景。 PID控制算法
    的頭像 發(fā)表于 06-13 09:17 ?2810次閱讀

    如何對MD5加密算法優(yōu)化?

    有人針對程序安全啟動過程,進(jìn)行MD5算法的優(yōu)化嘛。目前采用標(biāo)準(zhǔn)算法,時間稍長,如果有人做過優(yōu)化的話,可以分享一下,謝謝。
    發(fā)表于 02-18 08:20

    AURIX TC397是否可以搭配Google TensorFlow的演算法去運算?

    請問各位大神,AURIX TC397 是否可以搭配 Google TensorFlow 的演算法 去運算??
    發(fā)表于 02-18 06:05

    電子發(fā)燒友

    中國電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會員交流學(xué)習(xí)
    • 獲取您個性化的科技前沿技術(shù)信息
    • 參加活動獲取豐厚的禮品