해밀턴 순환(Hamiltonian Cycle)이란 해밀턴 경로(Hamiltonian Path)의 마지막 정점에서 첫 번째 정점으로 다시 연결되는 간선이 존재하는 경로를 말합니다. 즉, 무방향 그래프에서 그래프의 모든 정점을 정확히 한 번씩만 방문하고 시작점으로 되돌아오는 순환 경로입니다.
알고리즘 구성 및 역할
이 프로그램은 백트래킹(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) {
// 마지막 정점에서 시작 정점(0번)으로 돌아갈 수 있는지 확인
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() {
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
동작 원리 요약
이 알고리즘은 깊이 우선 탐색과 백트래킹을 결합한 방식으로 동작합니다. 시작 정점(0번)을 고정한 뒤, 나머지 정점들을 하나씩 경로에 추가해 봅니다. isSafe() 함수가 인접 여부와 중복 방문 여부를 검사하고, 더 이상 진행이 불가능하면 직전 단계로 되돌아가(path[pos] = -1) 다른 정점을 시도합니다. 모든 정점을 방문했을 때 마지막 정점이 시작 정점과 인접해 있다면 유효한 해밀턴 순환이 완성됩니다.
해밀턴 순환 문제는 NP-완전(NP-Complete) 문제로 알려져 있어, 이 백트래킹 기반 구현의 최악의 경우 시간 복잡도는 O(N!)입니다. 따라서 정점 수가 많은 그래프에는 적합하지 않지만, 작은 크기의 그래프에서는 효과적으로 동작합니다.