java - 遍历期间从图中删除节点

Question

我试图在对其进行拓扑遍历之前从定义的图(org.jgrapht.Graph)中删除一个节点/节点集。

图表定义示例

        Graph<URI, DefaultEdge> g = new DefaultDirectedGraph<>(DefaultEdge.class);

        URI google = new URI("http://www.google.com");
        URI wikipedia = new URI("http://www.wikipedia.org");
        URI jgrapht = new URI("http://www.jgrapht.org");

        // add the vertices
        g.addVertex(google);
        g.addVertex(wikipedia);
        g.addVertex(jgrapht);

        // add edges to create linking structure
        g.addEdge(jgrapht, wikipedia);
        g.addEdge(google, jgrapht);
        g.addEdge(google, wikipedia);
        g.addEdge(wikipedia, google);

我们如何从这棵树中删除特定的节点，例如wikipedia(及其子节点，如果有的话)？

我尝试过 jgrapht library 中可用的不同遍历，但是它们都明确提到在遍历过程中不应修改图。尝试过的遍历:DepthFirst、RandomWalk、BreadthFirst、ClosestFirst、TopologicalOrder。

有什么方法可以以最佳方式从图中删除有/没有遍历的节点吗？

Answer 1

您可以使用BFS来实现这一点:

1. 创建一个“集”来存储边。
2. 假设您想从 a -> b -> c 中删除 b，那么您应该标记 a -> 的边缘>b 和 b -> c 将被删除(基本上将它们添加到集合中)。
3. 完成BFS后，您将有一组要删除的边，删除它们和节点。