해밀턴 순환(Hamiltonian Cycle)은 해밀턴 경로(Hamiltonian Path)의 마지막 정점에서 첫 번째 정점으로 이동하는 간선이 그래프에 존재하는 경우를 말합니다. 즉, 무방향 그래프에서 그래프의 모든 정점을 정확히 한 번씩만 방문하고 다시 시작점으로 돌아오는 경로입니다.
이 문제는 대표적인 NP-완전 문제 중 하나로, 일반적으로 백트래킹(Backtracking) 기법을 사용하여 해결합니다. 후보 정점을 하나씩 경로에 추가해 보고, 해답으로 이어지지 않으면 이전 단계로 되돌아가 다른 정점을 시도하는 방식입니다.
함수 구성 및 역할
시작
1. isSafe() 함수 : 해당 정점이 이전에 추가된 정점과 인접해 있는지,
그리고 아직 경로에 포함되지 않았는지 검사합니다.
2. hamiltonianCycle() 함수 : 백트래킹을 통해 해밀턴 순환 문제를 해결합니다.
3. hamCycle() 함수 : hamiltonianCycle()을 호출하여 문제를 해결합니다.
해밀턴 순환이 존재하지 않으면 false를 반환하고,
존재하면 true를 반환하며 경로를 출력합니다.
끝예제 코드
#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<<"\nCycle does not exist"<<endl;
return false;
}
displaytheSolution(path);
return true;
}
void displaytheSolution(int p[]) {
cout<<"Cycle Exists:";
cout<<" Following is one Hamiltonian Cycle \n"<<endl;
for (int i = 0; i < N; i++)
cout<<p[i]<<" ";
cout<< p[0]<<endl;
}
int main() {
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;
}실행 결과
Cycle Exists: Following is one Hamiltonian Cycle 0 4 1 2 3 0
위 실행 결과는 0 → 4 → 1 → 2 → 3 → 0 순서로 모든 정점을 한 번씩 방문한 뒤 시작점으로 돌아오는 해밀턴 순환이 발견되었음을 보여줍니다. 만약 그래프에 해밀턴 순환이 존재하지 않는다면 "Cycle does not exist"라는 메시지가 출력됩니다.