Hamiltonian Path와 Cycle: 모든 정점을 정확히 한 번 방문하기

Hamiltonian Path는 그래프의 모든 정점을 정확히 한 번씩 방문하는 경로입니다.

Hamiltonian Cycle은 여기에 마지막 정점에서 시작 정점으로 돌아오는 조건이 추가된 순환 경로입니다.

Path와 Cycle의 차이

Hamiltonian Path:

A → B → C → D

Hamiltonian Cycle:

A → B → C → D → A

Eulerian Path와의 차이

Hamiltonian 문제는 정점에 초점을 둡니다.

모든 Vertex를 정확히 한 번

Eulerian 문제는 간선에 초점을 둡니다.

모든 Edge를 정확히 한 번

TSP와의 관계

Hamiltonian Cycle은 가능한 순환 경로의 존재를 묻습니다.

TSP는 가중치를 추가하여 가능한 Hamiltonian Cycle 중 최소 비용을 찾습니다.

Backtracking

사용하지 않은 이웃을 선택하고 재귀적으로 진행합니다.

막다른 경로에 도달하면 이전 선택을 취소하고 다른 후보를 시도합니다.

JavaScript 예제

function findHamiltonianPath(graph) {
  const nodes = Object.keys(graph);

  function search(current, path, used) {
    if (path.length === nodes.length) {
      return [...path];
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(next, path, used);

      if (result) return result;

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(start, [start], new Set([start]));
    if (result) return result;
  }

  return null;
}

복잡도

단순 Backtracking의 최악 시간 복잡도는 대략:

O(V!)

입니다.

Bitmask Dynamic Programming을 사용하면 약:

O(V² × 2^V)

으로 개선할 수 있지만 여전히 지수 시간입니다.

문제의 난이도

Hamiltonian Path와 Hamiltonian Cycle의 결정 문제는 대표적인 NP-Complete 문제입니다.

실제 활용

• 중복 없는 방문 순서
• Route Sequencing
• 그래프 퍼즐
• TSP의 구조적 기반
• 작업 순서 설계

언제 사용하나?

모든 정점을 정확히 한 번 사용해야 하고, 그러한 순서의 존재나 실제 순서를 찾는 것이 핵심일 때 적합합니다.

정리

Hamiltonian은 정점을, Eulerian은 간선을 중심으로 합니다. 작은 그래프에서는 Backtracking이 실용적이지만 큰 그래프에서는 DP, Pruning 또는 특수 알고리즘이 필요합니다.