java - 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来查找图形的最小顶点覆盖。该组的恭维将给您最大的独立组。