1

我在 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）。任何帮助，将不胜感激

4

3 回答 3

3

你想要 WeakComponentClusterer：http: //jung.sourceforge.net/doc/api/edu/uci/ics/jung/algorithms/cluster/WeakComponentClusterer.html

于 2013-06-19T00:55:39.830 回答
3

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

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 个顶点不应该是一个限制因素。

于 2013-07-02T21:44:27.653 回答
2

简单的 BFS 将为您提供答案...从任何节点启动您的 BFS，您会发现所有节点都可以从它访问...然后再次从另一个尚未访问的节点启动 BFS，依此类推...

于 2013-06-17T17:20:23.393 回答