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 找到图的最小顶点覆盖。该集的补充将提供您的最大独立集。