해밀턴 순환이란?
해밀턴 순환(Hamiltonian Cycle)은 그래프 이론에서 매우 중요한 개념입니다. 무방향 그래프에서 모든 정점을 정확히 한 번씩만 방문하는 경로를 해밀턴 경로(Hamiltonian Path)라고 하며, 이 경로의 마지막 정점에서 시작 정점으로 돌아가는 간선이 존재할 때 이를 해밀턴 순환이라고 부릅니다.
즉, 해밀턴 순환은 그래프의 모든 정점을 딱 한 번씩 거쳐 다시 출발점으로 되돌아오는 닫힌 경로입니다. 이 문제는 NP-완전(NP-Complete) 문제에 속하기 때문에, 일반적으로 백트래킹(backtracking) 기법을 사용하여 해결합니다.
알고리즘 구성 요소와 역할
이 프로그램은 세 가지 핵심 함수를 중심으로 동작합니다.
시작
1. isSafe() 함수 : 새로 추가하려는 정점이
이전 정점과 인접해 있는지, 아직 경로에 포함되지
않았는지를 검사합니다.
2. hamiltonianCycle() 함수 : 백트래킹을 통해 해밀턴
순환 문제를 실제로 해결합니다.
3. hamCycle() 함수 : hamiltonianCycle()을 호출하여 문제를
처리합니다. 해밀턴 순환이 존재하지 않으면 false를 반환하고,
존재하면 true를 반환한 뒤 경로를 출력합니다.
끝C++ 전체 소스 코드
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define N 5
using namespace std;
void displaytheSolution(int path[]);
bool isSafe(int n, bool g[N][N], int path[], int pos)
{
// 이전 정점과 인접하지 않으면 안전하지 않음
if (g [path[pos-1]][n] == 0)
return false;
// 이미 경로에 포함된 정점이면 안전하지 않음
for (int i = 0; i < pos; i++)
if (path[i] == n)
return false;
return true;
}
bool hamiltonianCycle(bool g[N][N], int path[], int pos)
{
// 모든 정점이 해밀턴 순환에 포함된 경우
if (pos == N)
{
// 마지막 정점에서 첫 번째 정점으로 가는 간선이 있는지 확인
if (g[ path[pos-1] ][ path[0] ] == 1)
return true;
else
return false;
}
for (int n = 1; n < N; n++)
{
// 해당 정점을 해밀턴 순환에 추가할 수 있는지 검사
if (isSafe(n, g, path, pos))
{
path[pos] = n;
// 재귀 호출로 나머지 경로를 구성
if (hamiltonianCycle (g, path, pos+1) == true)
return true;
// 해답으로 이어지지 않으면 해당 정점 제거 (백트래킹)
path[pos] = -1;
}
}
return false;
}
bool hamCycle(bool g[N][N])
{
int *path = new int[N];
for (int i = 0; i < N; i++)
path[i] = -1;
// 정점 0을 경로의 시작점으로 지정.
// 그래프가 무방향이므로 순환이 존재한다면 어느 점에서든 시작 가능
path[0] = 0;
if (hamiltonianCycle(g, path, 1) == false)
{
cout<<"\n순환이 존재하지 않습니다"<<endl;
return false;
}
displaytheSolution(path);
return true;
}
void displaytheSolution(int p[])
{
cout<<"순환이 존재합니다:";
cout<<" 다음은 해밀턴 순환의 한 예입니다 \n"<<endl;
for (int i = 0; i < N; i++)
cout<<p[i]<<" ";
cout<< p[0]<<endl;
}
int main()
{
// 5개의 정점을 가진 그래프의 인접 행렬 표현
bool g[N][N] = {{0, 1, 0, 1, 1},
{0, 0, 1, 1, 0},
{0, 1, 0, 1, 1},
{1, 1, 1, 0, 1},
{0, 1, 1, 0, 0},
};
hamCycle(g);
return 0;
}실행 결과
순환이 존재합니다: 다음은 해밀턴 순환의 한 예입니다 0 4 1 2 3 0
동작 원리 정리
위 코드의 핵심 로직은 다음과 같습니다.
1. isSafe() 검증 단계
새 정점을 경로에 추가하기 전에 두 가지 조건을 확인합니다. 첫째, 현재 경로의 마지막 정점과 인접한지 확인하고, 둘째, 해당 정점이 이미 경로에 포함되어 있지 않은지 검사합니다.
2. 백트래킹 탐색
hamiltonianCycle() 함수는 재귀적으로 정점을 하나씩 경로에 추가합니다. 만약 어떤 정점을 추가한 뒤 해답으로 이어지지 않는다면, 해당 정점을 경로에서 제거(-1로 초기화)하고 다른 후보 정점을 시도합니다. 이것이 바로 백트래킹 기법입니다.
3. 종료 조건
pos가 N(정점의 개수)에 도달하면 모든 정점을 방문한 것이므로, 마지막 정점에서 시작 정점(0번)으로 가는 간선이 존재하는지 최종 확인합니다.
실행 결과에서 볼 수 있듯이, 이 그래프는 0 → 4 → 1 → 2 → 3 → 0 순서의 해밀턴 순환을 가지며, 모든 정점을 정확히 한 번씩 방문한 후 시작점으로 돌아옵니다.