Поиск всех гамильтоновых циклов

Question

Я пытаюсь реализовать метод добавления всех возможных гамильтоновых циклов в список с использованием рекурсии. До сих пор моя остановка условие не является достаточным, и я получаю «OutOfMemoryError: Java кучу пространства» в строке, которая добавляет вершину в список:

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; 
} 

Может кто-то пожалуйста предложить мне то, что я делаю неправильно или мой подход совершенно неверен?

EDIT: Как было предложено в комментариях, виновником был родительский массив, вызывающий бесконечный цикл. Я не смог его исправить, и я изменил массив, чтобы сохранить дочерний элемент. Теперь все, кажется, работает:

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; 
} 

Answer 1

Если вы ищете непересекающиеся гамильтоновые циклы here имеет реализацию, используя с возвратами.