hap*_*pps 5 algorithm tree
我很难理解tarjan的最不常见的祖先算法,有人可以用一个例子来解释我吗？....我在DFS搜索后被卡住了算法做了什么？
Pha*_*ung 9
我的解释将基于上面发布的维基百科链接 :).
我假设你已经知道在算法中使用的联合不相交结构.(如果没有请阅读它,你可以在"算法简介"中找到它).
基本思想是每次算法访问节点时x,其所有后代的祖先都将是该节点x.
x
因此,要找到r两个节点的最小共同祖先(LCA)(u,v),将有两种情况:
r
(u,v)
Node u是节点的子节点v(反之亦然),这种情况很明显.
u
v
节点u是第i个分支,v是节点的第j个分支(i <j)r,因此在访问节点之后u,算法回溯到节点r,这是两个节点的祖先,标记节点的祖先u作为r访问节点v.目前它访问节点v,因为u已标记为已访问(黑色),所以答案将是r.希望你明白!
归档时间：
12 年，3 月 前
查看次数：
3104 次
最近记录：
6 年，6 月 前