모든 해밀턴 사이클 찾기

Question

재귀를 사용하여 가능한 모든 해밀턴 사이클을리스트에 추가하는 방법을 구현하려고합니다. 지금까지 내 정지 상태가 충분하지 내가 "OutOfMemoryError가 : 자바 힙 공간"얻을 목록에 정점을 추가 라인 :

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 연결되지 않은 해밀턴 사이클을 찾는 경우 : 이제 모든 것이 작동하는 것 같다.