algorithm - Tarjan的最低共同祖先算法解释

Question

我很难理解 Tarjan 的最低共同祖先算法。有人可以举例说明吗？

我在 DFS 搜索后卡住了，这个算法到底做了什么？

Answer 1

我的解释将基于维基百科 link贴在上面:).

我假设您已经了解算法中使用的联合不相交结构。(如果没有请阅读它，您可以在“算法简介”中找到它)。

基本思想是每次算法访问节点x时，其所有后代的祖先都将是该节点x。

所以要找到两个节点(u,v)的最小共同祖先(LCA)r，会有两种情况:

• 节点 u 是节点 v 的子节点(反之亦然)，这种情况很明显。

• 节点u是第i个分支，v是节点r的第j个分支(i < j)，所以访问后节点u，算法回溯到节点r，是两个节点的祖先，将节点u的祖先标记为 r 并去访问节点v。此时它访问节点 v，因为 u 已经被标记为已访问(黑色)，所以答案将是 r。希望你能得到它!