Tarjan最近公共祖先算法解释

Question

我很难理解Tarjan的最近公共祖先算法，有人能用例子来解释一下吗？

在DFS搜索后，我陷入了困境，这个算法到底是做什么的？

- happs

Answer 1

我的解释将基于上面发布的维基百科链接 :).

我假设您已经了解了算法中使用的并查集数据结构。 （如果没有，请阅读“算法导论”中的相关内容）。

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

因此，要找到两个节点(u,v)的最近公共祖先（LCA）r，有两种情况：

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

• 节点u是节点r的第i个分支，节点v是节点r的第j个分支（i < j），所以在访问节点u后，算法回溯到节点r，它是两个节点的祖先，将节点u的祖先标记为r，并继续访问节点v。 当它访问节点v时，因为u已经被标记为访问过（黑色），所以答案将是r。希望您明白了！

- Pham Trung

---

当你找到节点u时，你如何知道节点r是节点u和节点v的祖先？我不明白你如何知道回溯到哪里才能找到节点r。 - lolololol ol

你知道联合不相交结构吗？该算法是基于此的。 - Pham Trung

Answer 2

我将使用CP-Algorithms的代码进行解释：

void dfs(int v)
{
    visited[v] = true;
    ancestor[v] = v;
    for (int u : adj[v]) {
        if (!visited[u]) {
            dfs(u);
            union_sets(v, u);
            ancestor[find_set(v)] = v;
        }
    }
    for (int other_node : queries[v]) {
        if (visited[other_node])
            cout << "LCA of " << v << " and " << other_node
                 << " is " << ancestor[find_set(other_node)] << ".\n";
    }
}

让我们概述算法的证明。

引理1：对于每个顶点v及其父节点p，在我们从p访问v并将v与p合并后，p和根v的所有子树中的所有顶点（即p和所有v的后代，包括v）将位于由p表示的一个不相交集中（即祖先[不相交集的根]是p）。

证明：假设树的高度为h。然后按照顶点高度进行归纳，从叶节点开始。

引理2：对于每个顶点v，在我们将其标记为已访问之前，以下陈述是正确的：

1. 每个v的父节点pi将在一个不相交集中，该集合包含pi和pi已经完成访问的pi子树中的所有顶点。

2. 到目前为止，每个已访问的顶点都在这些不相交集之一中。

证明：我们通过归纳法进行证明。对于根节点（高度为0的唯一顶点），该语句是空洞的真实性，因为它没有父节点。现在假设该语句对于所有高度为k的节点（k≥0）都成立，且v是一个高度为k+1的节点。让p成为v的父节点。在p访问v之前，假设它已经访问了它的子节点c1、c2、…、cn。由引理1可知，p和根节点c1、c2、…、cn的子树中的所有节点都在一个由p表示的不相交集合中。此外，在我们访问p之后的所有新访问的节点都是这个不相交集合中的节点。由于p的高度为k，我们可以使用归纳假设得出结论：v确实满足1和2。

现在我们准备证明算法。

声明：对于每个查询(u,v)，该算法输出u和v的最低公共祖先。

证明：不失一般性，假设我们在DFS中访问u之前访问v。那么v要么是u的后代，要么不是。

如果v是u的后代，根据引理1，我们知道u和v在由u表示的一个不相交集合中，这意味着ancestor[find_set(v)]是u，即正确答案。

如果v不是u的后代，则根据引理2，我们知道u必须位于其中一个不相交集合中，每个集合都由v的父节点在标记v时表示。让p成为不相交集合的代表顶点，其中包含u。根据引理2，我们知道p是v的父节点之一，并且u在p的已访问子树中，因此是p的后代。在我们访问完所有v的子节点之后，这些不会改变，因此p确实是u和v的公共祖先。要看到p是最低公共祖先，请假设q是p的子节点，其中v是后代（即如果我们从v返回根，q是我们到达p之前的最后一个父节点；q可以是v）。假设反证法，u也是q的后代。然后根据引理2，u既在由p表示的不相交集合中，又在由q表示的不相交集合中，因此该不相交集合包含两个v的父节点，这是一个矛盾。

- Elucidase