참조
도서
- 안티 라크소넨, 『알고리즘 트레이닝 : 프로그래밍 대회 입문 가이드』, 인사이트, 2022, p.242
영상
-
- 시청 필수가 아님. 참고를 위해 단 것
그래프 기본
완전 경로
그래프의 경로와 관련된 중요한 개념 두 가지를 살펴본다. 오일러 경로는 모든 간선을 정확히 한 번씩 지나는 경로이고, 해밀턴 경로는 모든 노드를 정확히 한 번씩 방문하는 경로이다. 언뜻 봐서는 유사한 개념이라고 생각하기 쉽지만, 이와 관련된 계산 문제는 매우 다르다.
오일러 경로
오일러 경로(Eulerian path) 는 그래프의 각 간선을 정확히 한 번씩 지나는 경로이다. 그러한 경로의 시작과 끝이 같은 노드인 경우를 오일러 회로(Eulerian circuit) 라고 부른다. 그림 9에 2번 노드에서 시작하여 5번 노드에서 끝나는 오일러 경로가 나와 있고, 그림 10에는 1번 노드에서 시작하고 끝나는 오일러 회로가 나와 있다.
-
그림 9. 그래프와 오일러 경로
-
그림 10. 그래프와 오일러 회로
무방향 그래프에서
오일러 경로와 오일러 회로가 존재하는지는 노드의 차수에 따라 결정된다. 먼저, 무방향 그래프에 오일러 경로가 있는 경우는 모든 간선이 같은 연결 컴포넌트에 속하고 다음 두 조건 중 하나를 만족하는 경우와 동치이다.
- 모든 노드의 차수가 짝수이거나,
- 정확히 두 노드의 차수가 홀수이고, 다른 모든 노드의 차수는 짝수이다.
첫 번째 경우, 오일러 경로는 곧 오일러 회로가 된다. 두 번째 경우, 차수가 홀수인 두 노드가 오일러 경로의 양 끝점이 되며 이때는 오일러 회로가 아니다. 그림 9의 그래프에서 1, 3, 4번 노드의 차수는 2이고, 2, 5번 노드의 차수는 3이다. 정확히 두 노드의 차수가 홀수이므로 2번 노드와 5번 노드가 양 끝점인 오일러 경로가 존재하며 오일러 회로는 존재하지 않는다. 그림 10의 그래프는 모든 노드의 차수가 짝수이므로 오일러 회로가 존재한다.
방향 그래프에서
방향 그래프에 오일러 경로가 존재하는지를 확인하기 위해서는 노드의 진입 차수와 진출 차수를 확인하면 된다. 방향 그래프에 오일러 경로가 존재하는 경우는 모든 간선이 같은 강결합 컴포넌트에 속하고 다음 두 조건 중 하나를 만족하는 경우와 동치이다. 1
- 모든 노드의 진입 차수와 진출 차수가 같거나,
- 한 노드의 진입 차수가 진출 차수보다 1 크고, 다른 한 노드의 진출 차수가 진입 차수보다 1 크며, 나머지 노드는 진입 차수와 진출 차수가 같다.
첫 번째 경우, 오일러 경로는 곧 오일러 회로가 된다. 두 번째 경우, 진출 차수가 큰 노드에서 시작해서 진입 차수가 큰 노드에서 끝나는 오일러 경로가 존재한다. 예를 들어 그림 11의 그래프에서 1, 3, 4번 노드의 진입 차수와 진출 차수는 모두 1이고, 2번 노드는 진입 차수가 1이고 진출 차수가 2이며, 5번 노드는 진입 차수가 2이고 진출 차수가 1이다. 그러므로 이 그래프에는 2번 노드에서 시작해서 5번 노드에서 끝나는 오일러 경로가 존재한다.
- 그림 11. 방향 그래프와 오일러 경로
경로 찾기
히어홀처 알고리즘(Hierholzer’s algorithm) 은 그래프의 오일러 회로를 찾는 효율적인 방법이다. 이 알고리즘은 여러 단계로 구성되어 있으며, 단계마다 회로에 새로운 간선을 추가한다. 물론 그래프에 오일러 회로가 있다고 가정하며, 그렇지 않은 경우엔 오일러 회로를 찾을 수 없다.
노드가 하나 있고 간선이 없는 빈 회로에서 알고리즘을 시작하고, 부분 회로를 추가하는 식으로 회로를 한 단계씩 확장해 나간다. 이 과정을 모든 간선이 회로에 추가될 때까지 진행한다. 회로를 확장하기 위해서는 회로에 속한 노드 중 회로에 포함되지 않은 진출 간선이 있는 노드 를 찾는다. 그리고 노드 에서 시작하여 아직 회로에 포함되지 않은 간선으로 이루어진 경로를 구성한다. 언젠가는 이 경로가 노드 로 돌아오게 되는데, 이 경로가 부분 회로가 된다.
그래프에 오일러 회로는 없지만 오일러 경로가 있는 경우에도 히어홀처 알고리즘을 적용할 수 있는데, 새로운 간선을 그래프에 추가하고 오일러 회로를 찾은 뒤, 그 간선을 제거하면 된다. 예를 들어 무방향 그래프에서는 차수가 홀수인 두 노드를 잇는 새로운 간선을 추가하면 된다. (오일러 경로가 가능한 홀수 차수 그래프에서, 홀수 노드 간에 간선을 추가하여 오일러 회로로 만든다. 그리고 추가한 간선을 제거한다)
- 그림 12. 히어홀처 알고리즘
그림 12에 히어홀처 알고리즘을 적용하여 무방향 그래프에서 오일러 회로를 찾는 과정의 예가 나와 있다. 먼저 부분 회로 을 추가하고, 다음으로 부분 회로 를 추가하며, 마지막으로 부분 회로 을 추가한다. 그러면 모든 간선이 회로에 추가되었으므로, 최종 결과는 오일러 회로가 된다.
- 꼭 작은 사이클을 포함하면서 가는 방법이 아니여도 동작한다.
조건
- 무방향 그래프
- 간선이 있는 정점들이 모두 연결되어 있어야 한다.
- 오일러 회로
- 홀수 차수 정점이 0개
- 간선이 있는 아무 정점에서 시작
- 오일러 경로
- 홀수 차수 정점이 2개
- 홀수 차수 정점 중 하나에서 시작
- 방향 그래프
- 오일러 회로
- 모든 정점에서 진입 차수와 진출 차수가 같으면 오일러 회로가 존재
- 간선이 있는 아무 정점에서 시작
- 오일러 경로
- 시작점
outdegree = indegree + 1 - 끝점
indegree = outdegree + 1 - 나머지
indegree = outdegree
- 시작점
- 오일러 회로
히어홀처 알고리즘 순서도
기존 회로 찾기
→ 회로 위에서 남은 간선이 있는 정점 찾기
→ 그 정점에서 새로운 부분 회로 만들기
→ 기존 회로에 부분 회로 삽입
→ 반복[조건에 맞는 시작 정점을 스택에 넣는다]
↓
[스택이 비어 있는가?]
├─ 예
│ ↓
│ [path를 뒤집는다]
│ ↓
│ [완료]
│
└─ 아니오
↓
[스택 맨 위 정점 u를 확인한다]
↓
[u에서 사용할 수 있는 간선이 있는가?] (무방향 - u에 연결된 사용하지 않은 간선 / 방향 - u에서 나가는 사용하지 않은 진출 간선)
├─ 예
│ ↓
│ [간선을 사용 처리한다]
│ ↓
│ [다음 정점 v를 스택에 넣는다]
│ ↓
│ [반복]
│
└─ 아니오
↓
[u를 스택에서 꺼내 path에 추가한다]
↓
[반복]n코드
참고
- [그래프] 오일러 회로 | JusticeHui가 PS하는 블로그
- 절차 참고
- [Algorithm] 오일러 경로 — AlgorFati의 개발 기록
- 다음 이미지 이후로 dfs 과정 참고
연습 문제
연습 코드
def euler(n, edges, directed=False):
"""
n : 정점 개수 (0 ~ n-1)
edges : 간선 리스트 [(u, v), ...] 방향 그래프면 u -> v
directed : True면 방향 그래프
반환 : 오일러 경로/회로의 정점 리스트, 없으면 None
"""
m = len(edges)
adj = [[] for _ in range(n)]
indeg = [0] * n
def add(u, v, i):
adj[u].append((v, i))
if directed:
indeg[v] += 1
else:
adj[v].append((u, i)) # 무방향은 양쪽에
for i, (u, v) in enumerate(edges):
add(u, v, i)
# ── 1. 시작점 / 끝점 찾기 ───────────────────────────────
if directed:
d = [len(adj[v]) - indeg[v] for v in range(n)] # 진출 - 진입
else:
d = [len(adj[v]) % 2 for v in range(n)] # 1이면 홀수 차수
odd = [v for v in range(n) if d[v]] # 균형이 깨진 정점
if len(odd) not in (0, 2):
return None
if odd:
start, end = odd
if directed:
if d[start] + d[end] != 0 or abs(d[start]) != 1:
return None # +1/-1 짝이 아님
if d[start] < 0:
start, end = end, start
add(end, start, m) # 2. 가상 간선 (가장 마지막에 추가)
src = end # end에서 출발 → 첫 간선이 가상 간선
else:
src = next((v for v in range(n) if adj[v]), 0)
# ── 3. 히어홀처 (회로만 찾으면 됨) ────────────────────────
total = m + bool(odd)
used = [False] * total
stack = [src]
circuit = []
while stack:
u = stack[-1]
if adj[u]:
v, i = adj[u].pop()
if used[i]: # 무방향에서 반대편 복사본
continue
used[i] = True
stack.append(v)
else:
circuit.append(stack.pop())
circuit.reverse()
if len(circuit) != total + 1:
return None # 안 쓴 간선이 남음 = 끊어진 그래프
# ── 4. 가상 간선은 맨 앞에 있으므로 그냥 잘라낸다 ────────
return circuit[1:] if odd else circuitFootnotes
-
이 조건에는 예외가 있는데, 다음에 나올 두 번째 조건을 만족하는 노드의 진입 차수가 1이고 진출 차수가 0이거나, 진입 차수가 0이고 진출 차수가 1인 경우에는 같은 강결합 컴포넌트에 속하지 않아도 오일러 경로가 존재할 수 있다. ↩