[1. 개요]
dfs 를 이용하여 해결 할 수 있는 문제 중 오일러 서킷은 다음과 같은 문제를 말한다.
- 그래프의 모든 edge 를 정확히 한번만 사용해서 시작점으로 되돌아 오는 경로
- 무방향 그래프, 방향 그래프 모두에서 해결 가능하다.
기본적으로 오일러 서킷이 존재 할 수 없는 경우
- 그래프가 두 개 이상의 컴포넌트로 나뉜 경우
- 차수가 홀수 인 정점이 존재하는 경우
=> 어떤 점으로 들어갔는데, 이 점의 차수가 1이면 나올 수 없다.
=> 이 점이 시작점이 아닌 경로의 끝점인 경우, 오일러 서킷을 완성 할 수 없다.
오일러 서킷이 존재 하는 경우
- 모든 정점의 차수가 짝수
=> 단, 방향 그래프에서는 incoming edge 개수와 outgoing edge 개수가 같아야 한다. - 모든 edge 가 하나의 컴포넌트에 포함
dfs 를 이용하여 해결 할 수 있는 문제 중 오일러 트레일은 다음과 같은 문제를 말한다.
- 모든 edge 를 한번 씩 사용하여, 시작점과 끝점이 다른 경로
- 오일러 서킷은 시작점과 끝점이 같다.
오일러 서킷을 이용하여, 오일러 트레일을 찾을 수 있다.
- a 에서 시작하여 b 에서 끝나는 오일러 트레일을 찾는다고 할 때,
- edge : (b, a) 를 그래프에 추가한다.
- 이제 이 그래프에서 a 에서 시작하는 오일러 서킷을 찾는다.
- edge : (b, a) 를 제거한다.
오일러 트레일이 존재할 수 있는 조건
- edge : (b, a) 추가 후, 오일러 서킷 조건을 만족해야 한다.
- 시작점과 끝점을 제외한 모든 정점은 짝수점 이고,
- 시작점과 끝점만 홀수점 이다.
방향 그래프라면
- 시작 정점에서는 outgoing edge 개수가 하나 더 많고,
- 종료 정점에서는 incoming edge 개수가 하나 더 많아야 하고
- 나머지 정점에서는 같아야 한다.
[2. 무방향 그래프에서 오일러 서킷]
기본적인 알고리즘 구조
- dfs 를 통해 circuit 에 사용할 edge 를 순서대로 수집 => circuit-1 완성
- 재귀 종료 후 리턴 되는 과정에서 아직 사용하지 않은 edge 가 남아있다면,
- 이 정점을 시작점으로 circuit-2 을 생성
- circuit-2 를 circuit-1 사이에 끼워 넣는다.
- 위 과정 반복
실제 구현은 조금 더 단순하게 할 수 있다.
- edge 를 순서대로 수집하지 않고,
- 재귀 호출이 끝나고 반환되는 시점에 푸쉬한다.
- 단, 전체 재귀 종료 후, 최종 결과를 한번 더 뒤집어야 한다.
=> 현재 circuit 에는 경로에 뒷 부분만 저장되어 있기 때문이다.
=> 그래서, 새로운 circuit 을 끼워 넣는 것이 단순해진다.
[3. 코드]
