我很难理解 Tarjan 的最低共同祖先算法。有人可以用一个例子来解释吗？
我在 DFS 搜索后卡住了，算法到底是做什么的？
问问题
4086 次
2 回答
10
我的解释将基于上面发布的维基百科链接:)。
我假设您已经知道算法中使用的联合不相交结构。（如果没有，请阅读它，您可以在“算法简介”中找到它）。
基本思想是算法每次访问一个节点x，其所有后代的祖先都将是该节点x。
因此，要找到r两个节点的最小共同祖先（LCA） (u,v)，将有两种情况：
Node
u是 node 的子节点v（反之亦然），这种情况很明显。节点
u是第i个分支，v是节点的第j个分支（i < j）r，所以在访问节点之后u，算法回溯到节点r，即两个节点的祖先，将节点的祖先标记u为r，然后去访问节点v。目前它访问节点v，因为u已经标记为已访问（黑色），所以答案将是r。希望你得到它！
于 2013-10-09T07:01:38.867 回答
1
我将使用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，就在我们将其标记为已访问之前，以下陈述是正确的：
每个 v 的父母 pi 将在一个不相交的集合中，该集合恰好包含 pi 和 pi 已经完成访问的 pi 的子树中的所有顶点。
到目前为止，每个访问过的顶点都在这些不相交的集合中。
证明：我们通过归纳进行。该语句对于根（高度为 0 的唯一顶点）是空洞的，因为它没有父级。现在假设对于 k ≥ 0 的每个高度为 k 的顶点，该语句成立，并假设 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 中访问 v 之前访问了 u。那么 v 是否是 u 的后代。
如果 v 是 u 的后裔，根据引理 1，我们知道 u 和 v 在一个由 u 表示的不相交集合中，这意味着祖先 [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 的父母，
于 2020-07-02T13:29:03.647 回答