使用 jgrapht 分割森林中的一棵树

Question

我有一个用 jgrapht 库表示的树，有多种类型的节点，我需要从特定的节点类型开始切割任何子树。

正如您在此示例中所看到的，该树代表 Java 类的源代码。我需要通过拆分从每个“Entry”节点类型开始的主树来创建多个 jgrapht 对象。总共我应该从这棵大树中得到 7 棵树。我使用的结构是DirectedPseudograph.

Answer 1

虽然我不是 100% 清楚你想要什么，但似乎有多种解决方法。从根节点的每个传出邻居开始，您可以运行深度优先搜索并记录返回的节点。DFS算法可达的节点属于同一子树。为此，您可以使用DepthFirstIterator您可以创建没有根节点的子图，例如使用AsSubgraph类。然后，您可以在生成的导出子图上调用ConnectivityInspector 。由于每个子树都是一个断开连接的图形组件，因此连接检查器将能够找到每个组件。顺便说一句，除非您需要伪图的功能，否则为了性能，最好使用 SimpleDirectedGraph。显然，后者不允许平行边或自环。