algorithm - 查找循环图中任意两个节点的公共(public)子节点(后代)列表

Question

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

Answer 1

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

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