2

無向グラフを作成するための次のコードがあります。

UndirectedGraph g = new SimpleGraph(DefaultEdge.class);
g.addVertex("1");
g.addVertex("2");
g.addVertex("3");
g.addVertex("4");
g.addEdge("1", "3");
g.addEdge("1", "4");
g.addEdge("2", "4");
g.addEdge("3", "4");

JGraphT ライブラリを使用して、このグラフの最大独立集合を見つけるにはどうすればよいですか?

閉まっている

このコードを追加しました

Set vertices = g.vertexSet();
Set covers = VertexCovers.findGreedyCover(g);
Set difference = new HashSet(vertices);
difference.removeAll(covers);
System.out.println(difference);
4

1 に答える 1

2

org.jgrapht.alg.VertexCoversグラフの最小頂点カバーを見つけるために使用できます。そのセットの賛辞は、最大の独立したセットを提供します。

于 2013-11-02T02:11:49.827 に答える