오일러 서킷이란
오일러 서킷은 그래프의 각 간선을 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 말한다. 대표적인 오일러 서킷의 사례는 한 붓 그리기이다.
오일러 서킷이 존재하려면 각 간선이 모두 한 컴포넌트 안에 있어야 하고 ( 서로 연결될 수 없는 위치에 간선이 존재해서는 안된다) 각 vertex에 연결된 엣지의 수 가 짝수여야 한다. 만약 홀수가 되면, 그 vertex에 들어와서 다시 나가는 경로가 존재하지 않게 되어 그 vertex에서 경로가 종료되기 때문이다.
오일러 서킷을 구하는 알고리즘
오일러 서킷은 dfs를 통해 재귀적으로 찾아낼 수 있다. 어떤 그래프가 주어 졌을 때 시작 정점부터 방문되지 않은 엣지를 따라서 계속해서 전진하는 함수를 생각해 보면, 이 함수를 통해 만들어지는 경로는 반드시 시작 정점에서 끝나게 된다. 모든 경로가 짝수이기 때문에 어떤 정점에서 모든 엣지가 방문되어 종료되는 경우는 시작 정점밖에 없기 때문이다.
이렇게 만들어진 경로를 역방향으로 다시 타고 올라가다 보면 아직 방문하지 않은 엣지를 가진 vertex를 만날 수 있다. 이 vertex에서 방문하지 않은 엣지에 대해 다시 원래 함수를 호출해 주면 새로운 서킷을 얻을 수 있고 이렇게 얻어진 서킷을 모두 합치면 오일러 서킷이 완성된다.
모든 vertex는 짝수 개의 엣지를 가지고 있기 때문에 이러한 논리가 성립된다.
이러한 함수를 실제로 구현하는 데에는 dfs가 쓰인다. 오일러 서킷을 만드는 함수 euler()를 dfs처럼 재귀적으로 호출한다고 생각해보자.
euler()함수는 현재 보고 있는 vertex에서 간선이 존재하면 그 간선을 따라 계속 전진한다. 이 때 한 번 지나친 간선은 다시 지나치지 않기 위해 간선을 제거한다. 새로 도착한 vertex에선 euler()함수를 재귀 호출한다. 이렇게 정점에 새로 도착할 때 마다 지나친 간선을 제거하면서 함수를 재귀 호출하게 되면, 결국 시작 정점에 도착해서 더 이상 이동할 간선이 없을 때 까지 반복되게 되는 것이다. 함수가 종료 되면 구하고자 하는 경로를 담은 컨테이너에 현재 vertex를 담는다.
이렇게 마지막으로 도착한 시작 정점에서 부터 함수가 종료되기 시작하면, 경로에 지나쳐온 vertex가 하나 씩 담기고 오일러 서킷이 완성되는 것이다.
여러 방향으로 나갈 수 있는 vertex에 대해서도 함수가 재귀적으로 호출 되었기 때문에 순서대로 경로에 저장된다.
시간 복잡도는 모든 엣지를 지나쳐야 하기 때문에 E, 함수가 한번 호출 될 때마다 vertex들을 한번 씩 확인하기 때문에 V가 되어 O(V*E)가 된다.
오일러 트레일
오일러 트레일은 오일러 서킷과 매우 유사하지만, 시작 정점에서 끝나는 것이 아니라 다른 정점에서 끝나는 경로를 말한다.
오일러 서킷과 많은 특징을 공유하고 있기 때문에 구하는 방법도 비슷하다. 주어진 그래프에서 시작 정점과 끝 정점에 간선을 추가해서 오일러 서킷과 같은 특성을 가진 그래프를 만들어 주고 오일러 서킷을 구하는 알고리즘을 실행시키고 더해줬던 간선을 제거하면 오일러 트레일을 구할 수 있다.
