[그래프]DFS - 오일러 서킷

오일러 서킷은, 그래프상의 모든 간선(Edge)을 한 번씩만 지나서 시작점으로 돌아오는 경로를 말한다. 

흔히, 한 붓그리기로 알려져 있는 것이다.

(위키 참조: https://en.wikipedia.org/wiki/Eulerian_path)

위 그림을 보면, 1-2-4-3-4-6-5-3-1 의 경로가 오일러 서킷이 된다.

오일러서킷을 구하는 방법은 다음과 같다. (DFS처럼, 경로를 따라가면서 재귀호출. But, DFS와 똑같진 않다.)

 - getEulerCircuit(u)함수는 u와 인접한 간선들을 모두 검사하면서, 

 - 아직 방문하지 않은 간선(u,v)가 있다면, 연결을 끊고, getEulerCircuit(v)를 호출

 - 더 이상 따라갈 간선이 없다면 종료하는데, 종료하기 직전에 u를 circuit벡터에 보관

 - circuit벡터를 reverse하면 오일러 서킷이 됨.

위 그림의 예를, 오일러서킷 구하는 방법으로 실제 시뮬레이션해보면,

  1) 1번에서 시작.  연결된 2번과 3번중에서, 먼저 2번에 대해서, 1-2연결 끊고, 재귀호출(2)

  2) 2번과 연결된 4번에 대해서, 2-4연결 끊고, 재귀호출(4)

  3) 4번과 연결된 3,6 중에서 3번에 대해, 4-3 연결끊고, 재귀호출(3)

  4) 3번에 대해 연결된 1,4,5번중에서 1번에 대해(가장 먼저 있는 것이기에), 3-1 연결 끊고, 재귀호출(1)

  5) 1번에 대해서 남아있는 연결이 없기에 종료하면서 push(1)  

    여기까지 진행된 경로를 되새겨보면 아래그림과 같다.

6) 재귀호출(1)이 종료되었기에, 이 재귀호출(1)을 호출한 재귀호출(3)이 계속이어서 진행.

   즉 재귀호출(3)에서, 3과 연결된 1,4,5번중에서 먼저 1번에 대해 처리한 것이고, 이제 4번에 대해서 처리

   3-4 연결 끊고, 재귀호출(4) 

7) 4번과 연결된 6번에 대해서, 4-6 연결 끊고, 재귀호출(6)

8) 6번과 연결된 5번에 대해서, 6-5 연결 끊고, 재귀호출(5)

9) 5번과 연결된 3번에 대해서, 5-3 연결 끊고, 재귀호출(3)

10)3번에서 주위를 봐도, 남아 있는 연결이 없기에 종료하면서 push(3)

11)상위 호출인 재귀호출(5)에서도, 남아있는 연결이 없기에, 종료하면서 push(5)

12)마찬가지로 6번에 대해서도 종료하면서 push(6)

13)마찬가지로 4번에 대해서도 종료하면서 push(4)

14)재귀호출(4)를 한 3번점에서 봐도 이제는 남아있는 연결이 없기에, 종료하면서 push(3)

15)마찬가지로 push(4)

16)push(2)

17)push(1)

18)push되어 있는 것을 역으로 보면 1-2-4-3-4-6-5-3-1 로, 오일러 서킷이 되었음을 알 수 있음.

코드로 짜보면 다음과 같다.

#include <stdio.h>

#include <vector>

#include <algorithm>

#include <limits.h>

#include <iostream>

 

using namespace std;

 

vector<vector<int>> adj;

void getEulerCircuit(int u, vector<int>& circuit){

         for (int v = 1; v < adj.size(); ++v){

                  while (adj[u][v] > 0){

                           adj[u][v]--;

                           adj[v][u]--;

                           getEulerCircuit(v, circuit);

                  }

         }

         circuit.push_back(u);

}

 

void printCircuit(vector<int>& circuit){

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

         for (int i = 0; i < circuit.size(); ++i) cout << circuit[i] << " ";   

         cout << endl;

}

 

int main(void){

         freopen("EulerCircuit.txt", "r", stdin);

         setbuf(stdout, NULL);

 

         int C, N, T;

         cin >> C;

 

         for (int test = 1; test <= C; ++test){

                  cin >> N;

                  adj = vector<vector<int>>(N+1,vector<int>(N+1,0));           

 

                  cin >> T;

                  int a, b;

                  for (int i = 0; i < T; ++i){

                           scanf("%d%d", &a,&b);

                           //방향성이 없기에, [a][b]와 [b][a] 둘다 ++ 해주는 것에 유의

                           adj[a][b]++;      adj[b][a]++;

                  }

                 

                  vector<int> circuit;

                  getEulerCircuit(1,circuit);

                  printCircuit(circuit);

         }

 

         return 0;

}

EulerCircuit.txt

1

6 8

1 2

1 3

2 4

3 5

4 6

5 6

3 4

4 3

실행결과

1 2 4 3 4 6 5 3 1

계속하려면 아무 키나 누르십시오 . . .

  

-끝-