英文:
Max Clique Optimization
问题
public static void maxClique(Graph graph, List<Integer> clique) {
// 获取最新添加到团中的节点
int currentValue = clique.get(clique.size() - 1);
if (clique.size() > max.size()) {
max = clique;
}
// 遍历每个节点
for (int i = 0; i < graph.size; i++) {
// 如果被检查的节点与当前节点相连且不是当前节点本身
if (graph.matrix[currentValue][i] == 1 && !clique.contains(i)) {
// 检查新的团是否比当前最大团更大
// 创建一个新的团并将当前团中的所有节点添加进去
ArrayList<Integer> newClique = new ArrayList<>();
newClique.addAll(clique);
// 添加新节点
newClique.add(i);
// 重复
if (makesNewClique(graph, clique, i)) {
maxClique(graph, newClique);
}
}
}
}
类的完整内容：https://pastebin.com/fNPjvgUm
邻接矩阵：https://pastebin.com/yypN9K4L
英文:
I'm trying to find the max clique in a graph (adjacency matrix), the graph can have up to 50 nodes. Currently, what I have starts taking forever when the graph sizes get to around n=40. Can anyone find any optimizations I can make?
public static void maxClique(Graph graph, List<Integer> clique) {
//Get the newest node added to the clique
int currentValue = clique.get(clique.size() - 1);
if (clique.size() > max.size()) {
max = clique;
}
// Check every node
for (int i = 0; i < graph.size; i++) {
// If the node being checked is connected to the current node, and isn't the current node
if (graph.matrix[currentValue][i] == 1 && !clique.contains(i)) {
//Check if the new clique is bigger than the current max.
//Make a new clique and add all the nodes from the current clique to it
ArrayList<Integer> newClique = new ArrayList<>();
newClique.addAll(clique);
//Add the new node
newClique.add(i);
//Repeat
if (makesNewClique(graph, clique, i)) {
maxClique(graph, newClique);
}
}
}
}
Full class contents: https://pastebin.com/fNPjvgUm
Adjacency matrix: https://pastebin.com/yypN9K4L
答案1
得分: 1
David Eisenstat的评论已经给出了答案，以下是我为那些以后会来这里的任何人编写的代码：
public void bronKerbosh(Set<Integer> p, Set<Integer> r, Set<Integer> x) {
if (x.isEmpty() && p.isEmpty() && r.size() > max.size()) {
max = new ArrayList<>();
max.addAll(r);
}
Object[] pArr = p.toArray();
for (Object vTemp : pArr) {
int v = (int)vTemp;
Set<Integer> newR = new HashSet<>();
newR.addAll(r);
newR.add(v);
bronKerbosh(intersect(p, neighbors(v)), newR, intersect(x, neighbors(v)));
p.remove(v);
x.add(v);
}
}
英文:
David Eisenstat 's comment had the answer, here's my code for anyone that comes here later:
public void bronKerbosh(Set<Integer> p, Set<Integer> r, Set<Integer> x) {
if (x.isEmpty() && p.isEmpty() && r.size() > max.size()) {
max = new ArrayList<>();
max.addAll(r);
}
Object[] pArr = p.toArray();
for (Object vTemp : pArr) {
int v = (int)vTemp;
Set<Integer> newR = new HashSet<>();
newR.addAll(r);
newR.add(v);
bronKerbosh(intersect(p, neighbors(v)), newR, intersect(x, neighbors(v)));
p.remove(v);
x.add(v);
}
}
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论