中所有Hamilton週期

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

可有人請建議我什麼我做錯了或者是我的方法完全不正確？

編輯： 如意見提出，罪魁禍首是父陣列，從而導致無限循環。我無法糾正它，我改變了數組來存儲子元素。現在，一切似乎工作：

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具有使用回溯實現個H圈。