[알고리즘] The Hamiltonian Circuits Problem

최원석·2024년 12월 17일

💫 The Hamiltonian Circuits Problem

주어진 그래프에서 모든 정점을 정확히 한 번씩 방문하고 출발점으로 돌아오는 경로(순환), 즉 해밀턴 순환(Hamiltonian Circuit)이 존재하는가?

📁 유망한 노드인지 판단여부

상태 이상 트리에서 기준이 되는 노드의 부모노드, 자식노드가 기준이 되는 노드와 같은지 판단한다.
- 부모 노드, 자식 노드와 색이 같다 ⇒ 유망하지 않다.
- 노드, 자식 노드와 색이 색이 같지 않다. ⇒ 유망하다.

📁 Graph Coloring

bool promising(index i) {
    int j;
    bool switch;

    // 현재 정점이 마지막 정점(n-1)일 경우, 시작 정점(0)으로 돌아갈 간선이 없는지 확인
    if (i == n - 1 && !W[vindex[n - 1]][vindex[0]])
        switch = FALSE;

    // 현재 정점이 1 이상일 때, 이전 정점(i-1)에서 현재 정점(i)으로의 간선이 없는지 확인
    else if (i > 0 && !W[vindex[i - 1]][vindex[i]])
        switch = FALSE;

    else {
        switch = TRUE; // 기본적으로 유망하다고 가정
        j = 1;

        // 현재 정점까지의 경로에서 중복된 정점이 있는지 검사
        while (j < i && switch) {
            if (vindex[i] == vindex[j]) // 동일한 정점이 경로에 다시 등장하면 유망하지 않음
                switch = FALSE;
            j++;
        }
    }

    return switch; // 유망 여부를 반환
}