java - 修剪有向图的叶分量

Question

给定一个有向图及其一些节点，如何修剪无法到达任何给定节点的节点。（我称它为叶组件，我不确定这是一个正确的术语）

是否有任何已知的算法可以有效地解决这个问题？

如果您能指出一些 Java 开源代码，那将是完美的。

谢谢。

Answer 1

从给定的一组节点开始进行广度优先搜索或深度优先搜索，并标记搜索遍历的所有节点。之后，所有未标记的节点都无法从您的给定节点集访问，并且可以被修剪。如果n是顶点数，m是边数，这将解决O(n + m)中的问题。

我个人更喜欢Tinkerpop Blueprints作为我在 JVM/Java/Scala 中进行图形处理的主要库。

Answer 2

如果我猜对了，您需要找到强连通分量，可以通过 2 次深度优先搜索在 O(n + m) 时间内找到。