JGraphT -最大独立集

Question

我有这样的代码来生成无向图：

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);

Answer 1

您可以使用org.jgrapht.alg.VertexCovers找到图的最小顶点覆盖。对这组的赞美会给你最大的独立集。