在一个环形图中，找到任意两个节点的共同子孙（后代）列表。

Question

我有一个循环有向图，想知道是否有任何算法（最好是最优算法）可以制作任意两个节点之间的共同后代列表？这与最低公共祖先（LCA）所做的几乎相反。

- user3684042

---

在一个循环图中，一个节点可以是其自身的后代。 - Abhishek Bansal

在循环图中，你实际上没有后代。你要找的是从两个源顶点都可以到达的顶点集合？ - biziclop

你的意思是“常见相邻节点列表”吗？ - Andrew_CS

对两个节点分别进行深度优先搜索，然后选择它们各自节点集的交集。 - Abhishek Bansal

我认为没有比使用深度优先搜索列举出从A和B可到达的所有节点并计算其交集更好的解决方案。你可以引入一些优化：如果你正在寻找A可到达的节点，并碰巧找到了B，那么你可以停止查找并列出从B可到达的所有内容。 - biziclop

Answer 1

如用户1990169所建议的，您可以使用深度优先搜索计算从每个起始顶点可达的顶点集，然后返回它们的交集。

如果您计划在同一个图上重复执行此操作，则可能值得先计算和压缩强连通分量到代表一组顶点的超级顶点。作为副作用，您可以获得超级顶点的拓扑顺序。这允许数据并行算法同时计算多个起始顶点的可达性。将所有顶点标签初始化为{}。对于每个起始顶点v，将标签设置为{v}。现在，按照拓扑顺序扫描所有顶点w，通过将其出边邻居x的标签设置为x的标签和w的标签的并集来更新w的标签。使用位集表示集合以实现紧凑高效的表示。缺点是我们不能像单个可达性计算那样进行修剪。

- David Eisenstat

---

不能将未在交集中的顶点视为已访问。想象一下这个图 A -> D 和 B -> C -> D（其中 A 和 B 是您的源）。从 B 可以到达 D，但只能通过必须先经过的 C。 - biziclop

如果发现一个源可以从另一个源到达，那么您可以避免计算交集。 - biziclop

如果您有超过2个输入（OP在评论中暗示了这一点），那么您可能仍然需要在最后找到交集，但它可以节省运行搜索算法的时间，因为它们将具有相同的可达节点。 - Andrew_CS

@Andrew_CS 不是完全相同的，但其中一个将包含另一个。 - biziclop

Answer 2

我建议使用深度优先搜索（DFS）。

For each input node
    Create a collection to store reachable nodes
    Perform a DFS to find reachable nodes
        When a node is reached
            If it's already stored stop searching that path // Prevent cycles
            Else store it and continue

Find the intersection between all collections of nodes

注意：如果你愿意，你可以轻松地使用BFS（广度优先搜索）来实现相同的逻辑。

---

当您实现此功能时，请记住还有一些特殊情况可以寻找以进一步优化您的搜索，例如：

• 如果输入节点没有任何顶点，则没有公共节点
• 如果一个输入节点（A）到达另一个输入节点（B），则A可以到达B所能到达的所有内容。这意味着算法不必在B上运行。
• 等等。

- Andrew_CS

Answer 3

为什么不直接反转边的方向并使用LCA呢？

- user5997716

---

你知道这会起作用，只是将你的答案陈述成一个问题吗？那么你应该让你的答案更有权威性。或者你不确定，只是根据 OP 的问题回答吗？那么这应该是一条评论，而不是一篇答案。 - Teepeemm