해밀턴 사이클(Hamiltonian Cycle): 개념 정리와 백트래킹 알고리즘 구현

무방향 그래프에서 해밀턴 경로(Hamiltonian Path)는 각 정점을 정확히 한 번씩만 방문하는 경로를 의미합니다. 그리고 해밀턴 사이클(Hamiltonian Cycle)은 해밀턴 경로 중 마지막 정점에서 첫 번째 정점으로 돌아가는 간선이 존재하여 경로가 하나의 순환을 이루는 경우를 말합니다.

이번 글에서는 주어진 그래프에 해밀턴 사이클이 존재하는지 판별하고, 만약 해밀턴 사이클이 있다면 그 경로까지 출력하는 방법을 다룹니다.

입력과 출력

입력:
그래프 G(V, E)의 인접 행렬(adjacency matrix)

출력:
알고리즘은 주어진 그래프의 해밀턴 경로를 찾습니다.
위 예시의 경우 결과는 (0, 1, 2, 4, 3, 0)입니다.
하나의 그래프에는 여러 개의 해밀턴 경로가 존재할 수 있습니다.
만약 해밀턴 경로가 존재하지 않는다면, 알고리즘은 false를 반환해야 합니다.

알고리즘

isValid(v, k)

입력 − 정점 v와 위치 k

출력 − 정점 v를 위치 k에 배치하는 것이 유효한지 여부를 검사합니다.

Begin
    if 노드(k-1)와 v 사이에 간선이 없다면,
        return false
    if v가 이미 사용된 정점이라면,
        return false
    return true; // 그 외의 경우는 유효함
End

cycleFound(node k)

입력 − 그래프의 노드 k

출력 − 해밀턴 사이클이 존재하면 true, 아니면 false

Begin
    if 모든 노드가 경로에 포함되었다면,
        if 노드 k와 0 사이에 간선이 존재한다면,
            return true
        else
            return false;

    for 시작점을 제외한 모든 정점 v에 대해 반복:
        if isValid(v, k)라면, // v가 유효한 경우
            경로에 v를 추가
            if cycleFound(k+1)이 true라면,
                return true
            그렇지 않으면 경로에서 v를 제거 (백트래킹)
    done
    return false
End

C++ 구현 예제

아래 코드는 백트래킹(backtracking) 기법을 활용하여 해밀턴 사이클을 찾는 전체 과정을 보여줍니다. 시작 정점을 0으로 고정한 뒤, 나머지 정점들을 하나씩 경로에 추가하며 유효성을 검사하고, 막히면 이전 단계로 되돌아가 다른 정점을 시도합니다.

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 1},
    {0, 1, 1, 1, 0},
};
    
/* int graph[NODE][NODE] = {
    {0, 1, 0, 1, 0},
    {1, 0, 1, 1, 1},
    {0, 1, 0, 0, 1},
    {1, 1, 0, 0, 0},
    {0, 1, 1, 0, 0},
}; */

int path[NODE];

void displayCycle() {
    cout<<"Cycle: ";

    for (int i = 0; i < NODE; i++)
        cout << path[i] << " ";
    cout << path[0] << endl;      //첫 번째 정점을 한 번 더 출력하여 순환 표현
}

bool isValid(int v, int k) {
    if (graph [path[k-1]][v] == 0)   //간선이 없는 경우
        return false;

    for (int i = 0; i < k; i++)   //이미 사용된 정점은 제외
        if (path[i] == v)
            return false;
    return true;
}

bool cycleFound(int k) {
    if (k == NODE) {          //모든 정점이 경로에 포함된 경우
        if (graph[path[k-1]][ path[0] ] == 1 )
            return true;
        else
            return false;
    }

    for (int v = 1; v < NODE; v++) {       //시작점을 제외한 모든 정점 탐색
        if (isValid(v,k)) {               //경로에 v를 추가할 수 있는 경우
            path[k] = v;
            if (cycleFound (k+1) == true)
                return true;
            path[k] = -1;                 //v가 해답에 포함되지 않는 경우 되돌림
        }
    }
    return false;
}

bool hamiltonianCycle() {
    for (int i = 0; i < NODE; i++)
        path[i] = -1;
    path[0] = 0; //첫 번째 정점을 0으로 설정

    if ( cycleFound(1) == false ) {
        cout << "Solution does not exist"<<endl;
        return false;
    }

    displayCycle();
    return true;
}

int main() {
    hamiltonianCycle();
}

실행 결과

Cycle: 0 1 2 4 3 0

실행 결과를 보면 경로가 0에서 시작하여 0으로 다시 돌아오는 것을 확인할 수 있습니다. 이처럼 마지막 정점과 시작 정점이 연결되어 있으므로 해당 그래프에는 해밀턴 사이클이 존재한다고 할 수 있습니다.