♟ 하이어홀처(Hierholzer) 알고리즘

관련글 :

작동 방식 (6번 문제)

https://waydd.tistory.com/135

 

 

1,  하이어홀처 알고리즘 이란

 

오일러 투어나 회로를 효율적으로 찾는 알고리즘
→ 오일러 투어 (= 오일러 회로) 가 존재한다는 전제하에 실제 경로를 구하는 효율적인 방법

• 모든 정점의 차수가 짝수인 연결 그래프에서 오일러 회로를 찾는 알고리즘으로 처음 제안
  → 현재 존재하는 간선을 재귀적으로 탐색하여 오일러 회로(사이클)를 구성하는 방식
  → 모든 간선을 한 번씩만 방문 + 역순 경로가 오일러 회로
  → 응용하여 오일러 경로도 구할 수 있음
• DFS와 스택을 활용 + 사이클 구성
• 먼저 오일러 경로나 회로 존재 조건을 확인해야 함
• 그래프가 오일러 회로 조건을 만족할 때 (무향 그래프 : 모든 정점 차수 짝수, 방향 그래프 : in=out)
  시작점에서 출발 → 사이클 생성 → 다른 미방문 간선이 남아 있는 정점에서 확장 → 전체 경로 합치기 (오일러 회로 완성)
• 오일러 경로 조건 만족할 때 (무향 : 두 개의 정점만 홀수 차수, 방향 : 시작점-끝점의 차수 차이가 1 나는 경우)
  하이어홀처 알고리즘 적용 후 마지막에 가상 간선을 끊어냄 (시작점과 끝점을 가상의 간선 으로 연결하면 회로 조건) 
• 시간 복잡도 : O(V + E) 혹은 O(E) (간선 중심)  (정점 수 V, 간선 수 E)
  → 실직적 비용은 간선 순회에 있음 (모든 간선 한 번씩 방문)

※ 동작 방식 (단계별 정리)
①  그래프에서 출발점(조건에 따라 선택) 고름
  → 조건에 따라 : 회로는 아무 점, 경로는 특정 홀수 차수 점
②  스택에 시작 정점을 넣기
③  스택의 맨위 정점에서 아직 사용하지 않은 간선이 있으면 따라가면서 스택에 push
  → 그 간선을 따라 다음 정점으로 이동하며 스택에 추가
④  더 이상 진행할 간선이 없으면 스택에서 정점 pop 하여 경로에 추가
⑤  모든 간선을 다 사용할 때까지 ③ ~ ④ 반복
⑥  결과 경로를 역순으로 뒤집으면 오일러 경로(또는 회로)가 됨

 

 

2. 예시 코드

 

- 오일러 회로 전용 ( Hierholzer )

from collections import defaultdict

def eulerian_circuit(edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    # 각 간선을 역순으로 정렬해야 stack pop 시 사전순으로 앞서는 것부터 사용 가능
    for u in graph:
        graph[u].sort(reverse=True)

    stack = ['A']  # 임의 시작점 (조건: 모든 정점의 차수 짝수)
    circuit = []

    while stack:
        u = stack[-1]
        if graph[u]:
            v = graph[u].pop()
            stack.append(v)
        else:
            circuit.append(stack.pop())

    return circuit[::-1]  # 역순 반환


# 예시: 오일러 회로 (시작과 끝이 같음)
edges = [('A','B'), ('B','C'), ('C','A')]
print(eulerian_circuit(edges))  
# 출력: ['A', 'B', 'C', 'A']

 

 

- 오일러 경로 구하기 (가상 간선 기법)

from collections import defaultdict

def eulerian_path(edges):
    graph = defaultdict(list)
    indeg = defaultdict(int)
    outdeg = defaultdict(int)

    for u, v in edges:
        graph[u].append(v)
        outdeg[u] += 1
        indeg[v] += 1

    # 각 간선 역순 정렬 (사전순 경로 보장용)
    for u in graph:
        graph[u].sort(reverse=True)

    # 시작점 결정: outdeg = indeg+1 인 정점
    start = None
    for node in set(indeg) | set(outdeg):
        if outdeg[node] == indeg[node] + 1:
            start = node
            break
    if not start:
        start = edges[0][0]

    stack = [start]
    path = []

    while stack:
        u = stack[-1]
        if graph[u]:
            v = graph[u].pop()
            stack.append(v)
        else:
            path.append(stack.pop())

    return path[::-1]


# 예시: 오일러 경로 (시작과 끝이 다름)
edges = [('A','B'), ('B','C'), ('C','D')]
print(eulerian_path(edges))
# 출력: ['A', 'B', 'C', 'D']

 

- 의사 코드 (무방향 그래프)

• 핵심 알고리즘 : 하이어홀처 (오일러 경로/회로 탐색)
• 로직 1줄 요약 : 스택을 이용해 간선을 하나씩 제거하며 경로를 구성, 마지막에 역순으로 뒤집으면 오일러 경로 완성
• 시간 복잡도 : O(E)

※ 핵심 포인트
①  오일러 경로/회로 존재 조건을 반드시 먼저 확인
②  스택을 활용해 DFS 식으로 간선을 모두 소모해야 함
③  간선은 중복 방문 불가 → 따라서 "사용한 간선 제거" 과정 필수
④  결과는 역순으로 뒤집어야 올바른 경로가 됨

def hierholzer(graph, start):
    stack = [start]
    path = []

    while stack:
        node = stack[-1]
        if graph[node]:  # 아직 사용하지 않은 간선이 있다면
            next_node = graph[node].pop()
            graph[next_node].remove(node)  # 무방향이므로 양쪽에서 제거
            stack.append(next_node)
        else:
            path.append(stack.pop())

    return path[::-1]  # 역순이 정답

 

3. 오일러 경로와 오일러 회로

 

- 오일러 경로(Euler Path)  (간선을 모두 1번씩 지나는 경로)

• 그래프에서 모든 간선을 정확히 한 번씩 방문하는 경로
• 시작점과 끝점이 같을 수도 있고, 다를 수도 있음

 

- 오일러 회로(Euler Circuit / Euler Tour)

• 오일러 경로 ⊃ 오일러 회로(=오일러 투어)
• 오일러 경로 중, 시작점과 끝점이 동일한 경우

※ 트리 전용 알고리즘에서의 오일러 투어 기법
- 트리에서 DFS 순회를 방문 시점(in/out)으로 기록 하는 기법 을 뜻함 (LCA, 서브트리 쿼리, 세그먼트 트리 등에 활용)
- 이때 투어는 간선을 모두 순회한다 는 아이디어에서 옴
- 본래 그래프의 오일러 회로와는 다른 개념
- 오일러 투어는 전통적, 그래프 차원에서의 정의 와 트리 알고리즘 으로서 사용되며, 사용 맥락에 따라 달라짐

 

 

- 오일러 경로/회로 존재 조건

• 무방향 그래프 의 경우,
  ①  모든 정점의 차수가 짝수 → 오일러 회로 존재 (특수한 오일러 경로)
  ②  홀수 차수를 가지는 정점이 정확히 2개 → 오일러 경로 존재 (시작-끝이 다름) 
• 방향 그래프 의 경우,
  ①  모든 정점에서 in-degree = out-degree → 오일러 회로 존재
  ②  시작점은 (out-degree = in-degree + 1), 끝점은 (in-degree = out-degree + 1) → 오일러 경로 존재