무향 그래프에서 DFS를 이용해 오일러 회로 찾기

(출처: 종만북)

 

오일러 회로, 트레일에 대한 설명을 지난 게시물에 간략하게 올렸는데요, 이번엔 DFS를 이용해 오일러 회로를 만드는 알고리즘을 알아보겠습니다.

 

Fig 1. 무향 그래프 예시

Fig 1.처럼 생긴 무향 그래프에서 오일러 회로를 찾아보겠습니다. 일단 딱 봐도 모든 정점이 짝수점이니 오일러 회로가 존재합니다.

문제는 어떻게 오일러 회로를 만들 것인가인데요, 0번 노드부터 DFS를 통해 시작점까지의 경로를 찾아보겠습니다.

그러면 (1) 2번 노드에서 3번(or 5번) 노드로 갈지, (2) 6번 노드로 갈지에 따라 DFS로 만들어진 회로가 오일러인지 아닌지가 결정됩니다. (2)로 가면 회로가 모든 간선을 포함하지 않죠. 그 때는 회로를 따라 뒤로 가면서 인접한 간선을 방문하지 않은 정점을 찾고, 그 정점부터 다시 DFS를 사용해 회로를 구한 뒤 두 회로를 합칩니다.

이런 과정을 회로가 모든 간선을 포함할 때까지 반복하면 오일러 회로를 찾을 수 있습니다.

 

vector<vector<int>> adj;	// 인접행렬

// 무향 그래프 인접행렬 adj가 있을 때 오일러 회로를 계산
// 결과로 주어지는 circuit을 뒤집으면 오일러 회로가 됨
void getEulerCircuit(int current, vector<int>& circuit) {
	for (int next=0; next<adj[current].size(); ++next)
		while (adj[current][next] > 0) {
			--adj[current][next];
			--adj[next][current];
			getEulerCircuit(next, circuit);
		}

	circuit.push_back(current);
}

이 코드가 재귀를 사용해 오일러 회로를 구하는 함수입니다. 재귀호출이 끝나고 반환할 때 결과를 추가하기 때문에 회로를 구해서 끼워넣는 코드가 따로 필요하지 않습니다.