Tarjan的最不共同的祖先算法解釋

Question

我有一個艱難的時間瞭解tarjan的最不常見的祖先算法有人可以用一個例子來解釋我嗎？....我在DFS搜索後卡住了算法做什麼？

Answer 1

我的解釋將基於上面發佈的wikipedia link :)。

我認爲你已經知道在算法中使用的聯合不相交結構。 （如果沒有請閱讀，可以在「Introduction to Algorithm」中找到它）。

基本思想是每次算法訪問一個節點'x'，其所有後代的祖先將是該節點'x'。

因此，要找到兩個節點（U，V），會出現兩種情況的最低共同祖先（LCA）R：

• 節點u是節點V（反之亦然）的孩子，這種情況很明顯。

• 節點u是第i個分支，v是節點'r'的第j個分支（i < j），所以在訪問節點u之後，算法返回到兩個節點的祖先節點r，mark節點u的祖先爲'r'並且去訪問節點v 當它訪問節點v時，由於u已經被標記爲拜訪（黑色），所以答案將是'r'。希望你明白！