그리디 알고리즘을 이용한 오일러 경로 Finding an Euler Path using greedy algorithm.(C++)

/*finding an Euler path using Greedy Algorithm

그리디 알고리즘을 이용해 오일러 경로를 찾는 알고리즘

  DFS와는 다르게 각각의 정점에서 아무 간선으로나 진행*하여 최대한 빠르게 끝 정점*에

 도달하고 경로를 저장한다음 중간에 무시하고 지나간  회로*들을 다시 탐색하여 경로 중간에

 추가시켜주는 방법을 사용하여 훨신 빠르다.

 

*어느 간선을 이용하던 끝정점에 도달하게끔 되어있다.

*여기서 말하는  끝정점은 더이상 진행할 간선이 존재하지 않아 고립되게 되는 점이다.

*지금 까지 남아있는 간선들만 보았을때 그 그래프는 차수가 짝수인 점들로 이루어진 그래프와 같아서 오일러 회로가 반드시 존재한다.

중간에 지나친 회로들을 찾는 방법 : 현재 저장된경로의 끝 정점부터 처음 정점까지* 하나하나

사용하지 않은 간선과 연결되있나 검사하면 된다.

그리고 중간에 회로가 추가되었을때 추가된 회로까지 포함하여 검사가 완료되지 않은 점들을

또 검사한다.

*반대방향도 상관 없다. 그냥 경로내의 모든 정점에 사용하지 않는 간선이 존재하는지 여부만 확실히 하면 된다



이러한 과정을 통해 오일러 경로를 구할 수 있다.

여기서는 경로를 두개의 스택을 이용하여 추가를 하지만, 연결 리스트를 사용하건 뭘 사용하건 만든사람 마음이다.
input:
n m / n<=100: the number of vertex m<=1000: the number of line
a b / a: one side of a line ,b: the other side of a line.
repeat m-1 time.
*/
#include <iostream>
#include <windows.h>
#include <vector>

using namespace std;

int line[100][100];
int n ,m;
void EulerPath(int start);    

int main(){
   
    int i,a,b;
    bool odd[100]={};
    int start=1,cnt=0;
   
    cin>> n >> m ;
   
    for(i=0;i<m;i++){
                     cin>>a>>b;
                    
                     line[a-1][b-1]++;
                     line[b-1][a-1]++;
                    
                     odd[a-1]=!odd[a-1];
                     odd[b-1]=!odd[b-1];
    }
    for(i=n-1;i>=0;i--){
                     if(odd[i]){
                                cnt++;
                                start=i;
                     }
    }
   
    if(cnt==2||cnt==0)EulerPath(start);
    else cout<<"오일러 경로 없음"<<endl;
   
    system("PAUSE");
   
    return 0;
}
/*
|(0)스택 1의 마지막원소에서 진행할 정점이 있다면, 가장 낮은 수의 정점을 스택1에 저장
|       그리고 간선을 제거.
|(1)만약 진행할 정점이 없으면,
|  |(0)남은 간선이 있으면, 스택 1에서 마지막 원소를 제거하고 스택2로 push
|  |(1)남은 간선이 없으면, 스택 2의 모든 원소를 pull해서 스택1에 순서대로 넣고 스택 1 출력.
 
위와 아래는 동치
(남은 간선이 존재하지 않는다.->마지막원소에서 더이상 진행할 정점이 없다.)
(마지막 원소에서 더 이상 진행할 정점이 존재한다.->남은 간선이 존재한다.)

|(0)남은 간선이 존재한다면
| |(1)스택 1의 마지막 원소에서 진행할 정점이 있다면, 그중 가장 낮은 수의 정점을 스택1에       | | push.
| |(2)스텍 1의 마지막 원소에서 진행할 정점이 없다면, 스택 1의 마지막 원소를 스택 2에 push
| |          .이후 스택1의 마지막 원소를 pop.
|(1)남은 간선이 존재하지 않는다면, 스택 2의 모든 원소를 스택의 윗부분부터 차례대로 스택1  |에 쌓은후 출력.
*/
void EulerPath(int start){
     int i;
     vector<int> v1;
     vector<int> v2;
     bool flag;
    
     v1.push_back(start);
    
     while(m>0){
                flag = true;
                for(i=0;i<n;i++){
                                 if(line[v1.back()][i]>0){
                                                          line[v1.back()][i]--;
                                                          line[i][v1.back()]--;
                                                          m--;
                                                          flag=false;
                                                          v1.push_back(i);
                                                          break;
                                 }
                }
               
                if(flag){
                     v2.push_back(v1.back());
                     v1.pop_back();
                }
     }
    
     for(i=0;i<v1.size()-1;i++)cout<< v1[i]+1 << "->";
     cout<<v1.back()+1;
     for(i=v2.size()-1;i>=0;i--)cout<<"->"<<v2[i]+1;
     cout<<endl;
    
     return;
}

실행결과               

6 8
1 2
3 4
1 3
6 2
4 3
5 6
5 3
1 4
1->2->6->5->3->1->4->3->4
Press any key to continue . . .