[Graph] DFS의 대표 예시 오일러 경로

들어가기 전

한붓그리기로도 알려진 문제 오일러 서킷은 그래프 이론에서 첫 번째로 연구된 문제로 유명하다. 오일러 서킷은 주어진 도형의 모든 선을 정확히 한 번씩 그리고 시작점으로 돌아오는 문제이다. 결론부터 말하자면, 간선들이 하나의 컴포넌트에 포함되어 있고(부분 그래프가 없고) 모든 정점의 차수가 짝수라면 오일러 서킷은 항상 존재한다. 

오일러 서킷을 찾아내는 알고리즘

노드 방문 여부는 이제 중요하지 않다.

# 슈도 코드

# 인접 행렬
adj = [[], ... ,[]]
answer = []

dfs(here):
    answer.append(here)
    
    for there in adj[here]:
        while(adj[here][there] > 0):
            # 방문할 간선을 지운다
            adj[here][there] -= 1
            # 무향 그래프라면
            # adj[there][here] -= 1
            
            dfs(there)
            
# 방향 그래프이기 때문에
answer.reverse()

시간복잡도

각 간선을 따라갈 때마다 dfs()를 호출하기 때문에 O(|E|)의 시간 복잡도를 가지고, 그 내부에서 다음 간선을 탐색할때 O(|V|)만큼의 시간 복잡도를 가지기 때문에 총 O(|E|*|V|)의 시간 복잡도를 가진다.

번외

오일러 트레일이란 시작하는 점과 끝나는 점이 다른 오일러 회로 문제이다. 시작점과 끝점에 간선을 하나 추가하고 나서 오일러 서킷 문제로 변환하면 똑같은 문제가 된다.