3

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

4

3 回答 3

2

正如 user1990169 建议的那样，您可以使用 DFS 计算从每个起始顶点可到达的顶点集，然后返回交集。

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

于 2014-08-22T14:32:51.647 回答
0

我建议使用 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 上运行。
  • 等等
于 2014-08-22T14:32:30.923 回答
0

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

于 2016-02-29T13:12:01.670 回答