오일러 경로·회로 판별과 Hierholzer 알고리즘 구현

오일러 경로 알고리즘은 모든 간선을 정확히 한 번 사용하는 경로를 찾는다. 무향 그래프에서는 간선이 있는 정점들의 연결성과 홀수 차수 정점 수를 먼저 확인하고, 조건을 만족하면 Hierholzer 알고리즘으로 실제 경로를 O(V + E)에 구성할 수 있다.

오일러 경로와 오일러 회로의 조건

무향 그래프에서 간선이 있는 정점들이 하나의 연결 성분에 속한다고 하자.

홀수 차수 정점 수	결과	시작점
0	오일러 회로 존재	간선이 연결된 아무 정점
2	열린 오일러 경로 존재	두 홀수 차수 정점 중 하나
그 밖의 수	오일러 경로 없음	없음

차수는 한 정점에 닿은 간선 수다. self-loop는 같은 정점에 두 번 닿으므로 차수에 2를 더한다. 같은 두 정점을 잇는 parallel edge도 각각 별도의 간선으로 센다.

NIST DADS는 오일러 경로를 모든 간선을 정확히 한 번 쓰는 경로로 정의한다. “모든 정점이 연결되어야 한다”는 문장은 고립 정점까지 포함하면 지나치게 강하다. 필요한 조건은 차수가 0보다 큰 정점들이 하나의 연결 성분에 있는 것이다.

왜 홀수 차수 정점은 0개 또는 2개여야 하나

경로의 중간 정점에는 들어오는 간선과 나가는 간선이 한 쌍씩 생긴다. 따라서 중간 정점에서 사용한 간선 수는 짝수다.

열린 경로에서는 시작점에 나가는 간선 하나, 끝점에 들어오는 간선 하나가 짝을 이루지 못한다. 이 두 정점만 홀수 차수가 될 수 있다. 시작점과 끝점이 같으면 남는 간선이 없으므로 모든 정점의 차수가 짝수다.

이 조건은 필요조건에 그치지 않는다. 연결된 무향 그래프에서는 충분조건이기도 하다. TUM의 Hierholzer 알고리즘 설명은 사용하지 않은 간선을 따라 cycle을 만들고, 아직 사용하지 않은 간선이 남은 정점에서 새 cycle을 만들어 기존 경로에 결합하는 과정을 보여 준다.

Python으로 실제 경로를 만든다

아래 구현은 무향 multigraph를 대상으로 한다. 간선마다 고유한 edge_id를 붙이므로 parallel edge와 self-loop도 서로 다른 간선으로 처리한다.

from collections import defaultdict
from collections.abc import Hashable, Iterable

Edge = tuple[Hashable, Hashable]


def euler_trail(raw_edges: Iterable[Edge]) -> list[Hashable]:
    edges = list(raw_edges)
    if not edges:
        return []

    adjacency: dict[Hashable, list[tuple[int, Hashable]]] = defaultdict(list)
    for edge_id, (u, v) in enumerate(edges):
        adjacency[u].append((edge_id, v))
        adjacency[v].append((edge_id, u))

    odd_vertices = [v for v, incident in adjacency.items() if len(incident) % 2]
    if len(odd_vertices) not in (0, 2):
        raise ValueError("오일러 경로가 없습니다: 홀수 차수 정점 수가 0 또는 2가 아닙니다.")

    start = odd_vertices[0] if odd_vertices else edges[0][0]

    # 고립 정점을 제외한 연결성 검사
    seen: set[Hashable] = set()
    pending = [start]
    while pending:
        vertex = pending.pop()
        if vertex in seen:
            continue
        seen.add(vertex)
        pending.extend(neighbor for _, neighbor in adjacency[vertex])

    if seen != set(adjacency):
        raise ValueError("오일러 경로가 없습니다: 간선이 여러 연결 성분에 흩어져 있습니다.")

    # Hierholzer: 사용한 간선을 건너뛰며 역순으로 경로를 완성한다.
    used = [False] * len(edges)
    cursor: dict[Hashable, int] = defaultdict(int)
    stack = [start]
    reverse_route: list[Hashable] = []

    while stack:
        vertex = stack[-1]
        incident = adjacency[vertex]

        while cursor[vertex] < len(incident) and used[incident[cursor[vertex]][0]]:
            cursor[vertex] += 1

        if cursor[vertex] == len(incident):
            reverse_route.append(stack.pop())
            continue

        edge_id, neighbor = incident[cursor[vertex]]
        cursor[vertex] += 1
        used[edge_id] = True
        stack.append(neighbor)

    route = reverse_route[::-1]
    if len(route) != len(edges) + 1:
        raise RuntimeError("모든 간선을 사용하지 못했습니다.")
    return route


edges = [
    ("A", "B"),
    ("B", "C"),
    ("C", "A"),
    ("A", "D"),
]

print(euler_trail(edges))

출력되는 정점 순서는 간선 저장 순서에 따라 달라질 수 있다. 중요한 불변조건은 인접한 정점 쌍이 입력의 서로 다른 간선 하나씩에 대응하고, 경로의 정점 수가 E + 1이라는 점이다. 위 그래프에서는 홀수 차수 정점 A와 D가 양 끝이 된다.

코드가 선형 시간에 동작하는 이유

각 무향 간선은 인접 리스트에 두 번 저장되지만 used[edge_id]가 실제 사용을 한 번으로 제한한다. cursor는 한 정점의 인접 리스트를 뒤로 되돌아가지 않고 끝까지 한 번만 이동한다.

• 인접 리스트 구성: O(E)
• 연결성 검사: O(V + E)
• 홀수 차수 검사: O(V)
• Hierholzer 순회: O(E)
• 전체 공간: O(V + E)

“복잡한 그래프에서는 오일러 알고리즘이 비효율적일 수 있다”는 일반화는 맞지 않는다. 인접 리스트와 간선 식별자를 사용하면 그래프 크기에 선형인 시간으로 판정하고 경로를 만들 수 있다. 입력 전체를 읽어야 하므로 이보다 본질적으로 훨씬 적은 시간만 쓰기도 어렵다.

구현할 때 자주 놓치는 경계

차수만 보고 연결성을 생략한다

서로 떨어진 두 cycle은 모든 정점의 차수가 짝수지만 하나의 오일러 회로로 이어지지 않는다. 간선이 있는 정점들의 연결성을 반드시 확인한다.

고립 정점을 실패로 처리한다

정점 목록을 별도로 받는 구현이라면 차수 0인 정점은 연결성 조건에서 제외한다. 지나야 할 간선이 없기 때문이다.

인접 정점만 저장해 parallel edge를 합친다

set으로 이웃만 저장하면 같은 두 정점 사이의 여러 간선을 잃는다. 간선 ID나 개수까지 보존해야 한다.

존재 판정과 경로 구성을 섞는다

홀수 차수 정점 수만 반환하는 함수는 경로의 존재 여부만 알려 준다. 실제 순서를 요구하는 문제라면 Hierholzer 단계까지 구현해야 한다.

방향 그래프 조건을 그대로 적용한다

방향 그래프는 in-degree와 out-degree의 균형, 방향을 무시한 연결성 또는 회로의 경우 강한 연결성 등 조건이 달라진다. 위 코드는 무향 그래프 전용이다.

정점 기준 문제와의 차이는 해밀턴 경로와 오일러 경로 비교, 다른 목적의 graph traversal은 다익스트라 최단경로 풀이에서 이어서 볼 수 있다.

정리

무향 그래프의 오일러 경로는 간선이 있는 정점들의 연결성과 홀수 차수 정점 수로 판정한다. 0개면 회로, 2개면 열린 경로가 존재한다. 간선 ID와 정점별 cursor를 둔 Hierholzer 구현은 parallel edge와 self-loop를 보존하면서 모든 간선을 선형 시간에 한 번씩 사용한다.

참고 자료

• NIST DADS: Eulerian path
• NIST DADS: Eulerian graph
• Technical University of Munich: Hierholzer's algorithm
• NetworkX: has_eulerian_path