[알고리즘이론] 오일러 회로(Euler circuit) 파이썬으로 구현하기

오일러 회로(Euler circuit)는 그래프 이론에서 모든 간선을 한 번씩만 지나는 경로가 존재하는 그래프를 말합니다. 이러한 경로를 오일러 경로(Euler path)라고 부르기도 합니다.

오일러 회로를 찾는 알고리즘 중 하나인 Hierholzer 알고리즘을 파이썬으로 구현해보겠습니다.

Hierholzer 알고리즘은 다음과 같은 단계를 따릅니다.

 

1. 임의의 시작점을 선택하여 stack에 넣습니다.
2. stack에서 노드 하나를 꺼내 이 노드에 연결된 간선들 중 아직 방문하지 않은 간선을 찾습니다. 해당 간선을 따라 다음 노드로 이동합니다.
3. 이동한 노드를 stack에 넣습니다. 이동한 간선은 삭제합니다.
4. 2~3번 과정을 반복합니다. 만약 더 이상 이동할 간선이 없다면 해당 노드를 result 리스트에 추가합니다.
5. stack이 비어있지 않은 동안 2~4번 과정을 반복합니다.
6. result 리스트의 역순으로 정렬한 후 반환합니다.

 

이러한 Hierholzer 알고리즘을 파이썬으로 구현한 코드는 다음과 같습니다. 아래 코드에서 그래프는 딕셔너리 형태로 주어집니다. 각 키는 그래프의 노드를 나타내며, 해당 노드와 연결된 노드들은 값으로 저장됩니다.

 

def find_euler_circuit(graph):
    # 시작점을 임의로 선택
    start = list(graph.keys())[0]
    stack = [start]
    result = []
    while stack:
        node = stack[-1]
        if graph[node]:
            # 이동 가능한 노드가 있으면 이동
            next_node = graph[node].pop()
            stack.append(next_node)
        else:
            # 이동할 수 있는 노드가 없으면 결과 리스트에 추가
            result.append(stack.pop())

    # 결과 리스트를 역순으로 정렬하여 오일러 회로를 구함
    return result[::-1]

 

위 코드에서는 시작점으로 그래프의 첫 번째 노드를 선택하고, stack에 해당 노드를 넣습니다. 이후 while문을 반복하며, stack에서 마지막으로 넣은 노드를 꺼냅니다. 해당 노드와 연결된 간선들 중 아직 방문하지 않은 간선을 찾아 다음 노드로 이동합니다. 이동한 노드를 stack에 넣습니다. 만약 더 이상 이동할 간선이 없다면 해당 노드를 result 리스트에 추가합니다.