[알고리즘이론] 오일러 경로(Eulerian path) 파이썬으로 구현하기

오일러 경로(Eulerian path)는 그래프의 모든 간선을 한 번씩만 방문하면서 출발점과 도착점이 다른 경로입니다. 파이썬으로 오일러 경로를 구하는 알고리즘은 다음과 같습니다.

1. 그래프가 오일러 경로가 되는지 확인합니다. 이를 위해서는 그래프가 무방향 그래프이고 모든 정점의 차수가 짝수이거나, 정확히 두 개의 정점의 차수가 홀수이어야 합니다.
2. 오일러 경로가 있다면 시작 정점을 선택합니다. 시작 정점은 차수가 홀수인 정점 중 임의의 하나를 선택하거나, 그렇지 않으면 아무 정점이나 선택할 수 있습니다.
3. 시작 정점에서 출발하여 갈 수 있는 경로가 있는 동안 이동합니다. 이동한 경로는 스택에 저장합니다.
4. 이동한 경로의 마지막 노드에서 출발하여 갈 수 있는 경로가 있는 동안 이동합니다. 이동한 경로도 스택에 저장합니다.
5. 경로를 이동할 수 없을 때, 스택에서 경로를 하나씩 꺼내면서 경로를 출력합니다.

파이썬 코드로 구현하면 다음과 같습니다.

def find_eulerian_path(graph):
    # 그래프가 오일러 경로가 되는지 확인
    odd_degree_vertices = [v for v in graph if len(graph[v]) % 2 == 1]
    if len(odd_degree_vertices) not in [0, 2]:
        return None

    # 시작 정점 선택
    start_vertex = odd_degree_vertices[0] if len(odd_degree_vertices) == 1 else list(graph.keys())[0]

    # DFS로 경로 탐색
    stack = [start_vertex]
    path = []
    while stack:
        v = stack[-1]
        if graph[v]:
            u = graph[v].pop()
            stack.append(u)
        else:
            path.append(stack.pop())

    return path[::-1]

이 함수는 인접리스트 형태의 그래프를 입력으로 받아, 오일러 경로를 반환합니다. 만약 그래프에 오일러 경로가 없다면 None을 반환합니다.