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

오일러 서킷이란?

깊이 우선 탐색을 이용해 풀 수 있는 유명한 문제로, 그래프의 모든 간성르 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제이다.

모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된 그래프가 주어진다면 항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다.

findRandomCircuit(u)는 u와 인접한 간선들을 하나하나 검사하면서, 아직 방문하지 않은 간선 (u,v)가 있다면 또다시 findRandomCircuit(v)를 호출. 더이상 

따라갈 간선이 없다면 재귀 호출 종료후 반환한다.

재귀 호출이 끝나고 반환할 때 경로에 추가해줌 으로서 경로의 끝점부터 역순으로 간선들이 추가된다.

코드 ( C+ + )

#include <iostream>

#include <vector>

using namespace std;

// 그래프의 인접 행렬 표현, adj[i][j] = i 와 j 사이의 간선의 수

vector<vector<int>> adj;

// 무향 그래프의 인접 행렬 adj가 주어질 때 오일러 서킷을 계산한다.

// 결과로 얻어지는 circuit을 뒤집으면 오일러 서킷이 된다.

void getEulerCircuit(int here, vector<int>& circuit)

{

for (int i = 0; i < adj.size(); ++i)

{

if (adj[here][i] > 0) {

adj[here][i]--; // 양쪽 간선을 모두 지운다.

adj[i][here]--;

getEulerCircuit(i, circuit);

}

}

circuit.push_back(here);

}

int main()

{

int n = 6;

adj = vector<vector<int>>(n, vector<int>(n, 0));

adj[0][1] = 1;

adj[1][2] = 1;

adj[2][4] = 1;

adj[2][3] = 1;

adj[4][5] = 1;

adj[5][2] = 1;

adj[3][0] = 1;

vector<int> circuit;

getEulerCircuit(0, circuit);

cout << "뒤집기 전 " << endl;

for (int i = 0; i < circuit.size(); ++i)

cout << circuit[i] << " ";

reverse(circuit.begin(), circuit.end());

cout << endl;

cout << "뒤집기 후 " << endl;

for (int i = 0; i < circuit.size(); ++i)

cout << circuit[i] << " ";

return 0;

}

참고 문헌 : 알고리즘 해결 전략