找到所有哈密顿循环 [英] Finding all hamiltonian cycles
问题描述
我正在尝试实现一种方法,使用递归将所有可能的哈密顿循环添加到列表中。到目前为止,我的停止条件还不够,我在列表中添加一个顶点的OutOfMemoryError:Java堆空间:
I'm trying to implement a method for adding all possible Hamiltonian cycles to a list using recursion. So far my stopping condition isn't sufficient and I get "OutOfMemoryError: Java heap space" in the line that adds a vertex to a list:
private boolean getHamiltonianCycles(int first, int v, int[] parent,
boolean[] isVisited, List<List<Integer>> cycles) {
isVisited[v] = true;
if (allVisited(isVisited) && neighbors.get(v).contains(new Integer(first))) {
ArrayList<Integer> cycle = new ArrayList<>();
int vertex = v;
while (vertex != -1) {
cycle.add(vertex);
vertex = parent[vertex];
}
cycles.add(cycle);
return true;
} else if (allVisited(isVisited)) {
isVisited[v] = false;
return false;
}
boolean cycleExists = false;
for (int i = 0; i < neighbors.get(v).size(); i++) {
int u = neighbors.get(v).get(i);
parent[u] = v;
if (!isVisited[u]
&& getHamiltonianCycles(first, u, parent, isVisited, cycles)) {
cycleExists = true;
}
}
//if (!cycleExists) {
isVisited[v] = false; // Backtrack
//}
return cycleExists;
}
有人可以告诉我我做错了什么或完全是我的做法不正确?
Can someone please suggest me what I'm doing wrong or is my approach completely incorrect?
编辑:
正如评论中所建议的那样,罪魁祸首是父数组,导致无限循环。我无法纠正它,我更改了数组以存储子元素。现在一切似乎都有效:
As suggested in comments, the culprit was the parent array, causing an infinite loop. I wasn't able to correct it and I changed the array to store the child element. Now everything seems to work:
private boolean getHamiltonianCycles(int first, int v, int[] next,
boolean[] isVisited, List<List<Integer>> cycles) {
isVisited[v] = true;
if (allVisited(isVisited) && neighbors.get(v).contains(first)) {
ArrayList<Integer> cycle = new ArrayList<>();
int vertex = first;
while (vertex != -1) {
cycle.add(vertex);
vertex = next[vertex];
}
cycles.add(cycle);
isVisited[v] = false;
return true;
}
boolean cycleExists = false;
for (int u : neighbors.get(v)) {
next[v] = u;
if (!isVisited[u]
&& getHamiltonianCycles(first, u, next, isVisited, cycles)) {
cycleExists = true;
}
}
next[v] = -1;
isVisited[v] = false; // Backtrack
return cycleExists;
}
推荐答案
如果您正在寻找Disjoint Hamiltonian Cycles 此处有一个使用回溯的实现。
If you is looking for Disjoint Hamiltonian Cycles here have an implementation using Backtracking.
这篇关于找到所有哈密顿循环的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!