找到所有哈密顿循环
我正在尝试实现一种方法，使用递归将所有可能的哈密顿循环添加到列表中。 到目前为止，我的停止条件还不够，我在向列表中添加顶点的行中得到“OutOfMemoryError：Java堆空间”：
private boolean getHamiltonianCycles(int first, int v, int[] parent, boolean[] isVisited, List<List> cycles) { isVisited[v] = true; if (allVisited(isVisited) && neighbors.get(v).contains(new Integer(first))) { ArrayList 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; } 有人可以告诉我我做错了什么，或者我的方法完全不正确？
编辑：正如评论中所建议的那样，罪魁祸首是父数组，导致无限循环。 我无法纠正它，我更改了数组以存储子元素。 现在一切似乎都有效：
private boolean getHamiltonianCycles(int first, int v, int[] next, boolean[] isVisited, List<List> cycles) { isVisited[v] = true; if (allVisited(isVisited) && neighbors.get(v).contains(first)) { ArrayList 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 ，请使用Backtracking实现。