有向图的LCA问题
来源：13-6 拓扑排序
讲武德的年轻人
2022-07-28
bobo老师，我最近在做leetcode 1650问题中的关于的二叉树的lowest common ancestor问题。这个题目没有root的指针，除了left, right外，还额外有parent指针。在学习有向图中我想，如果这个问题抽象成图论该如何解决？比如，给定一个图，被告知任意两点之间的child-parent关系，据此可以建图，但是每个child可能有多个parent。这种情况下，给定任意两个结点，如何求得这两个结点的lowest common ancestor?因为每个节点的parent不唯一，所以LCA也可能有多个。我能想到的是可以用dfs来解决，但是感觉不是很好。不知道图论上有没有专门的算法解决这个问题？谢谢！
写回答
1回答
-
我没有听说过“专门”的图上的 LCA 算法，至少这不属于图论的“经典算法”（一般图论书中不会描述这个问题）。
但是要是出这么一个算法问题，肯定是可以解决的。我粗想如下：
1）首先，在 G 的反图中 dfs 或者 bfs 标记 u 的所有祖先；
2）在 G 的反图中再一次 dfs 或者 bfs，对于已经标记是 u 的祖先的节点，标记同时也是 v 的祖先。这一步之后，相当于就找到了 u 和 v 的所有公共祖先。我们把他们叫候选节点。
3）对于 2）中求出的所有候选节点，如果一个候选节点没有其他的候选节点的孩子，就是 u 和 v 的一个 LCA 节点。
继续加油！：）
012022-07-29
相似问题