有向无环图中的一组最不常见的祖先
Set of Least Common Ancestors in a Directed Acyclic Graph
我有一个节点层次结构需要用于分析。有点像这样
我正在尝试找到一种算法，使我能够找到两个节点之间最近的共同祖先。我知道有一些算法可以找到最低的共同祖先，但我还没有找到一种算法可以让我们找到最近的几个。
例如，在我上面链接的图片中，如果我给它两个节点：0 和 1，它应该 return 2 和 5。即它应该 return 的所有共同祖先没有后代的节点也是共同的祖先。一种天真的方法是获取 0 和 1 的所有共同祖先：{7, 5, 6, 3, 2}，然后消除 7，因为它在集合中有后代。然后它也会消除 6 和 3。所以它会 return SLCA = {5,2}。目前，我已将每个节点的所有祖先存储在一个列表中。所以这种天真的做法是可行的。但是，我想做一个更有效的方法，即使是非常大的图也可以扩展。最终，对于给定的图，我希望能够计算每对节点的成对 SLCA。我认为这种蛮力方法对于非常大的图来说会很慢。
有人知道这样的算法吗？我一直在阅读这些论文，但它们非常密集，而且我一直在努力理解它们。
https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/LCA-Max-witness.pdf
http://www.ccs.neu.edu/home/dherman/browse/projects/mini-javac/papers/bender01finding.pdf
https://algo2.iti.kit.edu/download/fischer10new.pdf
https://algo2.iti.kit.edu/download/fischer10new.pdf
感谢您的帮助
Well actually your "brute force" algorithm is quite efficient. Let's analyze it:
找到所有共同祖先，您可以使用两个 BFS 和一个数组来完成此操作，该数组保留两棵树中的节点：时间 - O(V + E)，内存：O(V).
现在你可以找到组中所有没有后代的祖先，也就是离根最近的所有节点。这不会花很长时间，取这个组的子图并在 O(V + E) 时间（通过遍历节点）和 O(V) 内存中找到一个没有传入边的节点。这就是您的答案。
总计 - 时间 O(V + E)，内存 O(V)。
The next answer is not the correct answer, it finds the closest common ancestor (I have written it by mistake and I don't really want to delete it):
复制图形，现在我们有 G1 和 G2。对于 G1 中的每个节点，创建一条新边到 G2 中的相应节点。 'Flip' G2 中的所有边 - 如果有从 v 到 u 的边，现在它是从 u 到 v.
调用这个新图 G，调用找到 SLCA 所需的两个节点 u 和 v。
很容易证明，从G1中的u到G2中对应的v的最短路径会经过一条从G1的边] 到 G2 并且这条边的节点（这条边上的两个节点都是对应的）将在 SLCA 组中。
那是因为如果你看原图，我们从每个节点v，u走的路径是最短相遇的，这就是SLCA组的定义。
现在你需要找到所有最短路径长度的路径并提取所有这些节点。
时间：O(E + V)（最短路径 - BFS）
内存：O(V) (BFS)
我有一个节点层次结构需要用于分析。有点像这样
我正在尝试找到一种算法，使我能够找到两个节点之间最近的共同祖先。我知道有一些算法可以找到最低的共同祖先，但我还没有找到一种算法可以让我们找到最近的几个。
例如，在我上面链接的图片中，如果我给它两个节点：0 和 1，它应该 return 2 和 5。即它应该 return 的所有共同祖先没有后代的节点也是共同的祖先。一种天真的方法是获取 0 和 1 的所有共同祖先：{7, 5, 6, 3, 2}，然后消除 7，因为它在集合中有后代。然后它也会消除 6 和 3。所以它会 return SLCA = {5,2}。目前，我已将每个节点的所有祖先存储在一个列表中。所以这种天真的做法是可行的。但是，我想做一个更有效的方法，即使是非常大的图也可以扩展。最终，对于给定的图，我希望能够计算每对节点的成对 SLCA。我认为这种蛮力方法对于非常大的图来说会很慢。
有人知道这样的算法吗？我一直在阅读这些论文，但它们非常密集，而且我一直在努力理解它们。
https://www.dcs.warwick.ac.uk/~czumaj/PUBLICATIONS/DRAFTS/LCA-Max-witness.pdf
http://www.ccs.neu.edu/home/dherman/browse/projects/mini-javac/papers/bender01finding.pdf
https://algo2.iti.kit.edu/download/fischer10new.pdf
https://algo2.iti.kit.edu/download/fischer10new.pdf
感谢您的帮助
Well actually your "brute force" algorithm is quite efficient. Let's analyze it:
找到所有共同祖先，您可以使用两个 BFS 和一个数组来完成此操作，该数组保留两棵树中的节点：时间 - O(V + E)，内存：O(V).
现在你可以找到组中所有没有后代的祖先，也就是离根最近的所有节点。这不会花很长时间，取这个组的子图并在 O(V + E) 时间（通过遍历节点）和 O(V) 内存中找到一个没有传入边的节点。这就是您的答案。
总计 - 时间 O(V + E)，内存 O(V)。
The next answer is not the correct answer, it finds the closest common ancestor (I have written it by mistake and I don't really want to delete it):
复制图形，现在我们有 G1 和 G2。对于 G1 中的每个节点，创建一条新边到 G2 中的相应节点。 'Flip' G2 中的所有边 - 如果有从 v 到 u 的边，现在它是从 u 到 v.
调用这个新图 G，调用找到 SLCA 所需的两个节点 u 和 v。
很容易证明，从G1中的u到G2中对应的v的最短路径会经过一条从G1的边] 到 G2 并且这条边的节点（这条边上的两个节点都是对应的）将在 SLCA 组中。
那是因为如果你看原图，我们从每个节点v，u走的路径是最短相遇的，这就是SLCA组的定义。
现在你需要找到所有最短路径长度的路径并提取所有这些节点。
时间：O(E + V)（最短路径 - BFS）
内存：O(V) (BFS)