我已经在 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
顶点的 Set
(集合)。基本上,它看起来像:
{ <---+
{1,2,3},{4,5}, <--- a set of vertices |
{1,2},{3},{5}, |- a set of sets
{1},{2,3,4}, |
... |
} <---+
顺便说一句,该算法的速度将取决于您拥有的顶点数(如您正确所述)以及边数。但是 100,000 个顶点不应成为限制因素。
关于java - 使用 JUNG 查找图中不连通的子图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/17152621/