我一直在嘗試從維基百科學習Tarjan算法3個小時，但我無法制作它的頭部或尾部。 :(我如何學習Tarjan的算法？
http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1
爲什麼這是DFS樹的子樹？（實際上DFS產生森林？O_O） 又爲何v.lowlink=v.index意味着v是根？
能有人請解釋這給我/給這個算法背後的直覺或動機？
想法是：當遍歷樹時，每次你搜索了一個分支並且回溯，你檢查你是否遇到過一個邊樹中'上'節點。
如果你沒有（if (v.lowlink = v.index)），那麼你剛剛完成的SCC - 它由當前節點和棧上的所有節點。這完全是DFS樹的一個子樹，除了已完成的SCC中的節點之外。
如果確實如此，則將此信息傳播到'上'節點（v.lowlink := min(v.lowlink, w.lowlink)），因爲與DFS樹中的路徑結合，邊會創建「向上」路徑。
DFS產生一個森林，但你總是考慮一棵樹。一個SCC總是包含在一個DFS樹中，否則（作爲一個SCC）在兩個（所有）樹之間將存在兩個方向的路徑 - 這是矛盾的。
只是添加到pjotr的答案：v.lowlink基本上是您在樹中找到的最高節點的索引。請記住，在這種情況下，最重要的意思是最小化，因爲您在走下時保持增加指數。現在處理所有的繼任者後，有三個基本情況：
v.lowlink < v.index：這表明你已經找到了底部。請注意，我們沒有找到任何後端，但是指向一個位於當前「之上」的節點。這就是v.lowlink < v.index所暗示的。
v.lowlink = v.index：我們知道在這種情況下，沒有後邊緣指向當前節點上的任何東西。這個節點可能有一個後端邊緣（這意味着你的後繼節點之一w有一個低鏈接，例如w.lowlink = v.lowlink = v.index）。也可能是後邊緣指的是當前節點下方的某個東西，這意味着當前節點下面有一個強連通的組件，已經打印出來了。然而，當前節點絕對是強連通組件的根源。
v.lowlink> v.index：這實際上是不可能的。爲了完整起見，我只是列出它。 ;）
希望它有幫助！
直覺性有關的Tarjan的算法：
DFS過程中，當我們從頂點v遇到一個背邊，我們更新了最低可達祖先即我們更新的值低[V]
現在，當一個頂點的所有輸出邊被處理時，即我們即將退出頂點v的DFS調用時，我們檢查low [v]的值，是否低[v] == v（下面的解釋） 。如果不是這意味着v不是SCC的根，那麼我們現在給v的父親帶來好處，即父母[v]的最低可達祖先現在變爲低[v]。
這聽起來邏輯彷彿雖然有從父[V]到v的祖先沒有直接的後邊緣，但有通過該父母的路徑（V +朝向V邊緣的後邊緣） [v]仍然可以達到v。 的祖先因此，我們也在這裏更新了低[parent [v]]。 因此，我們將繼續更新這個鏈，所有v的低[v]將不斷更新，直到我們到達祖先（通過回溯）。因爲這個祖先低[v]將等於v，因此這將作爲SCC的根。
希望這會有幫助
對不起，鏈接斷了，不知道如何使它工作。請只複製整個鏈接。 –
斷開鏈接固定;使用「Globe」圖標在選定的文本上使用特定的URL。 :) – Akarun
注意。謝謝:) –