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

모든 정점이 짝수점(정점의 차수가 짝수인 점)이고, 모든 간선이 하나의 컴포넌트에 포함되어 있다고 가정하자.

 

함수 findRandomCircuit(u) : 현재 정점에 인접한 간선 중 아직 따라간 적 없는 임의의 간선을 재귀적으로 따라가기를 반복하다가, 더이상 따라갈 간선이 없을 때 종료.

 

함수를 실행하면 여러 부분 서킷이 생성될텐데, 전체를 포함하는 하나의 서킷을 원하므로 모든 부분 서킷들을 합쳐야한다.

 

부분 서킷이 생긴다는 말은 무슨 말일까?

어떤 정점에서부터 출발하는 간선이 하나가 아닌 여러개일 수 있는데, 이때 서킷의 정의에 따라 출발하는 간선만큼 해당 정점으로 오는 간선이 존재해야한다. -> 그만큼 부분서킷이 생긴다.

해당 정점에서 나가는 간선이 2개 존재한다면, 2개의 부분 서킷이 생긴다. 이 부분서킷들을 합쳐 하나의 서킷을 만들 수 있다.

 

findRandomCircuit(u) 함수의 return  과정은 서킷 생성의 역방향으로 이루어진다.

그러므로 return 하면서 vector에 추가해준 후, 함수가 최종적으로 종료하면 vector를 뒤집으면 서킷을 얻을 수 있다.

 

 

vector<vector<int>> adj;
// adj[i][j] = i와 j 사이의 간선 수
 
// 무향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷을 계산한다.
// 결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다.
void getEulerCircuit(int here, vector<int>& circuit)
{
    for(int there=0;there<adj.size();++there)
    {
        while(adj[here][there] > 0)
        {
            adj[here][there]--;
            adj[there][here]--;
            getEulerCircuit(there, circuit);
        }
    }
    circuit.push_back(here);
}

 

각 간선을 따라갈 때마다 getEulerCircuit() 함수를 호출하고, 그 내부에서는 O(|V|)의 반복문을 수행하기 때문에 이 알고리즘의 전체 시간복잡도는 O(|V||E|) 가 된다.