有向无环图中寻找最低公共祖先的算法？
设想一个有向无环图如下所示，其中：
- “a”是根（总是正好有一个根）
- 每个节点都知道其父节点
- 节点名称是任意的-不能从中推断出任何内容
- 我们从另一个来源了解到，节点是按照A到G的顺序添加到树中的（例如，它们是在版本控制系统中提交的）
我可以使用什么算法来确定两个任意节点的最低共同祖先(LCA)，例如：
-
null
注：
- 从根到给定节点不一定只有一条路径（例如“g”有两条路径），所以不能简单地遍历从根到两个节点的路径并寻找最后一个相等的元素
- 我发现了树的LCA算法，特别是二叉树，但它们不适用于这里，因为一个节点可以有多个父节点（即这不是一棵树）
共有1个答案
Den Roman的链接（存档版本）似乎很有希望，但对我来说有点复杂，所以我尝试了另一种方法。下面是我使用的一个简单算法：
假设您想用x和y两个节点计算LCA(x，y)。每个节点必须有一个值color和count。初始化为白色和0。
- 将x的所有祖先涂成蓝色（可以使用BFS）
- 将y的所有蓝色祖先涂成红色（又是BFS)
- 对于图中的每个红色节点，将其父节点的
计数增加一个
可以有一个以上的解决方案，这取决于您的图表。例如，考虑以下图：
LCA(4,5）可能的解是1和2。
注意，如果您想找到3个或更多节点的LCA，它仍然有效，您只需要为每个节点添加不同的颜色。
-
我的问题是树中有大量的节点和许多查询。是否有一种算法，它进行预处理，使查询能够在恒定的时间内得到答复。 我研究了使用RMQ的LCA，但我不能使用该技术，因为我不能对树中的这么多节点使用数组。 如果知道它是满二叉树，节点之间的关系如上所示，那么有人能给我一个高效的实现来快速回答许多查询。 但是当有很多查询时，这种算法非常耗时，因为在最坏的情况下，我可能必须遍历30的高度（树的最大高度）才能到达根（最
-
我的问题是：“这是已知算法的已知问题吗？”。我怀疑是。它似乎非常类似于拓扑排序。我有一个基于合并排序的算法的想法，但如果已知的算法已经存在，就没有理由提出我自己的算法。
-
68.1 二叉查找树 题目链接 Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree 解题思路 在二叉查找树中，两个节点 p, q 的公共祖先 root 满足 root.val >= p.val && root.val <= q.val。 // java public TreeNode lowestCommonAncestor
-
我试图通过自顶向下递归实现二叉树最低公共祖先(LCA)问题的解决方案。 我使用的方法是： 想法：找到在任一子树中有一个所需节点的节点，而另一个所需节点是相反的子树。 以下是确切的实现： 例如： 这将返回树的根作为结果。结果=TreeNode(2)
-
问题内容： 这是一个受欢迎的面试问题，我唯一可以找到的有关该主题的文章是TopCoder的文章。对我来说不幸的是，从访谈答案的角度来看，它看起来过于复杂。 除了绘制到两个节点的路径并推导祖先之外，没有其他更简单的方法了吗？（这是一个很流行的答案，但是面试题有一个变体，要求一个固定的空格答案）。 问题答案： 恒定空间答案：（尽管不一定有效）。 有一个函数findItemInPath（int inde
-
我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用维基百科中的最长路径问题算法。我已经让算法适用于大多数图形，但对于其他图形，它没有给出正确的结果。算法为： 图形实现使用邻接列表来存储图形。如果我传递一个图，例如： 我得到的答案5，这是正确的。但是，如果我通过图表： 然后我得到2，而正确答案应该是3。 我使用的TopSort2算法是： DFS 算法包括：