java - 使用JUNG查找图中的断开连接的子图

我已经在Java中使用JUNG创建了图形

Graph<Integer, String> g;
public SimpleGraphView2() {
    // Graph<V, E> where V is the type of the vertices and E is the type of the edges

    g = new SparseGraph<Integer, String>();
    // Add some vertices. From above we defined these to be type Integer.
    g.addVertex((Integer)1);
    g.addVertex((Integer)2);
    g.addVertex((Integer)3);
    g.addVertex((Integer)4);
    g.addVertex((Integer)5);
    g.addVertex((Integer)6);
    g.addVertex((Integer)7);
    g.addVertex((Integer)8);

    g.addEdge("A", 1, 2);
    g.addEdge("B", 2, 3);
    g.addEdge("C", 2, 4);
    g.addEdge("D", 4, 5);
    g.addEdge("E", 1, 3);
    g.addEdge("F", 6, 7);
    g.addEdge("G", 7, 8);
}

我想在创建的图形g中找到断开连接的图形的数量。因此，在我的情况下，我希望输出为2（第一个图形包含：1、2、3、4、5。第二个图形包含：6、7、8）。任何帮助，将不胜感激

最佳答案

约书亚给你正确的答案。一个例子是：

Transformer<Graph<V,E>, Set<Set<V>>> trns = new WeakComponentClusterer<V,E>();
Set<Set<V>> clusters = trns.transform(graph);

这将为您提供clusters，它是顶点Set的Sets（集合）。基本上，它看起来像：

{                                                    <---+
   {1,2,3},{4,5},       <--- a set of vertices           |
   {1,2},{3},{5},                                        |- a set of sets
   {1},{2,3,4},                                          |
   ...                                                   |
}                                                    <---+

顺便说一句，该算法的速度将取决于您拥有的顶点数量（如您正确声明的那样）以及边的数量。但是100,000个顶点不应成为限制因素。