algorithm - 如果是图，如何定义 LCA（最小公共祖先）（两个节点）？

Question

我用谷歌搜索并试图在图中找到关于 LCA（两个节点）的信息，但不幸的是，我没有找到太多描述性和可理解的内容。

那么请有人可以在图表中详细说明 LCA（有向和无向）吗？

Answer 1

要在有向图中找到最接近两个节点的共同祖先，请从每个节点向上进行广度优先搜索。在访问节点时将每个节点添加到节点向量中，每次搜索一个节点。搜索完成后，找到两个向量中的第一个公共节点。

优化：当搜索深度增加时暂停搜索。如果找到了共同节点，则停止，否则继续下一个深度。