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が含まれます。2番目には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あることがわかります。基本的には、次のようになります。SetSets

{                                                    <---+
   {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 に答える