有向图的LCA问题

Question

bobo老师，我最近在做leetcode 1650问题中的关于的二叉树的lowest common ancestor问题。这个题目没有root的指针，除了left, right外，还额外有parent指针。在学习有向图中我想，如果这个问题抽象成图论该如何解决？比如，给定一个图，被告知任意两点之间的child-parent关系，据此可以建图，但是每个child可能有多个parent。这种情况下，给定任意两个结点，如何求得这两个结点的lowest common ancestor?因为每个节点的parent不唯一，所以LCA也可能有多个。我能想到的是可以用dfs来解决，但是感觉不是很好。不知道图论上有没有专门的算法解决这个问题？谢谢！

Answer 1

liuyubobobo 2022-07-29 01:58:01

我没有听说过“专门”的图上的 LCA 算法，至少这不属于图论的“经典算法”（一般图论书中不会描述这个问题）。

但是要是出这么一个算法问题，肯定是可以解决的。我粗想如下：

1）首先，在 G 的反图中 dfs 或者 bfs 标记 u 的所有祖先；

2）在 G 的反图中再一次 dfs 或者 bfs，对于已经标记是 u 的祖先的节点，标记同时也是 v 的祖先。这一步之后，相当于就找到了 u 和 v 的所有公共祖先。我们把他们叫候选节点。

3）对于 2）中求出的所有候选节点，如果一个候选节点没有其他的候选节点的孩子，就是 u 和 v 的一个 LCA 节点。

继续加油！：）

• 提问者 讲武德的年轻人 #1

  谢谢bobo老师。这种方法很好，除了最近ancestor，应该也可以用来求解最远ancestor，只要在候选点里找到parent为null的就行了。