[C++ 알고리즘] 오일러 회로 / 오일러 경로 (Euler ciruit / Euler trail)

오일러 회로 문제

 : 그래프의 모든 간선을 한 번씩만 지나면서, 모든 정점을 들린 뒤 시작점으로 돌아오는 문제.

다른 조건은 만족하되, 시작점으로 돌아오지 않아도 되는 문제는 오일러 경로 문제이다.

 

 

어떠한 양방향 그래프가 주어졌을 때, 오일러 회로 또는 경로가 존재할 수 있는지 판단할 수 있는

필요충분조건 두 가지가 존재한다.

 

양방향 그래프에서 오일러 회로 또는 경로가 존재하기 위한 필요충분조건

 

1.

모든 정점이 하나의 컴포넌트 안에 속해 있는가?

(좌)오직 하나의 컴포넌트  / (우)두 개로 나누어진 컴포넌트

이를 확인하기 위해서 사용할 수 있는 방법 중 하나는,

한 정점에 대하여 dfs 또는 bfs를 사용해서 탐색을 한 번 마친 뒤, 방문하지 않은 정점이 존재할 경우 두 개 이상의 컴포넌트가 존재함을 알아낼 수 있다.

 

int chk[N];
int adj[N][N]; //adj[i][j] : i에서 j로 가는 간선의 수

void chk_dfs(int N)
{
    chk[N]++; //방문했음을 표시
    for(int i=0;i<N;i++)
    {
        if(!chk[i] && adj[n][i]) chk_dfs(i);
    }
}

bool chk_only_component()
{
    chk_dfs(0);
    for(int i=0;i<N;i++)
    {
        if(chk[i] == 0) return false;
    }
    return true;
}

 

2.

(오일러 회로의 경우) 모든 정점의 차수(간선의 수)가 짝수인가? 

(오일러 경로의 경우) 두 정점을 제외한 모든 정점의 차수가 짝수인가? (차수가 홀수인 두 정점은 각각 출발점, 도착점이 된다.)

 

간선의 개수가 짝수여야하는 이유는 나갈 때 사용할 간선의 수와 들어올 때 사용할 간선의 수가 같아야 하기 때문이다.

( a + a = 2 * a )

 

//간선의 수가 짝수인지 확인하는 코드

int degree[N]; //degree[i] : i번 정점의 차수
int stNode; //오일러 경로에서 시작점이 될 수 있는 정점
bool chk_Euler()
{
    int odd = 0;
    for(int i=0;i<N;i++)
    {
    	if(degree[i] %2 ==1) 
        {
            odd++;
            stNode = i;
        }
    }
    return odd ==0 || odd == 2; //odd == 0 이면 오일러 회로 존재, odd == 2면 오일러 경로 존재
}

위 두 가지 조건이 True가 되는 양방향 그래프는 항상 오일러 회로 / 경로를 갖는다.

 

오일러 회로 / 경로 구하기

오일러 회로와 경로를 구하는 방법은 dfs(깊이 우선 탐색)을 이용하면 정말 간단하게 해결할 수 있다.

 

다음 정점으로 이동하는 간선이 있을 경우, 이용한 간선을 지우면서 다음 정점으로 재귀호출 한다.

더 이상 이동할 수 없을 때까지 함수를 재귀호출 한 뒤에, 함수를 리턴하면서 현재 정점을 배열에 추가한다.

배열을 reverse 하면 오일러 회로 / 경로가 나오게 된다.

stack을 사용하면 reverse를 사용하지 않아도 구할 수 있다.

 

//오일러 경로 / 회로 구하는 코드

int stNode;
int degree[N]
int adj[N][N]; //adj[i][j] : i -> j로 가는 간선의 수

void dfs(int n, stack<int>& E)
{
	for (int i = 0; i < n; i++)
	{
		if (adj[n][i] > 0)
		{
			//양방향 그래프이므로 양쪽으로 지워준다
			adj[n][i]--;
			adj[i][n]--;
			dfs(i, E);
		}
	}
	E.push(n);
}

stack<int> get_Euler()
{
	stack<int> E;
	dfs(stNode, E);
}

int main()
{
	//입력 및 필요충분조건 확인 함수 생략
	stack<int> Euler;
	Euler = get_Euler();
	while(!Euler.empty())
        {
            cout<<Euler.top()<<' ';
            Euler.pop();
        }
}

 

 그래프가 단방향 그래프일 때의 오일러 회로

오일러 문제는 그래프가 단방향 그래프일 경우 필요한 Variable이 추가되며, 그에 따라 필요충분조건 확인 방법과 오일러 회로를 구하는 방법이 살짝 바뀌게 된다.

 

단방향 그래프에서 오일러 회로 / 경로가 존재할 수 있는 필요충분조건

 

1.

모든 정점이 하나의 컴포넌트에 속한다.

 

2.

모든 정점에 대해서, 나가는 간선의 수와 들어오는 간선의 수가 같다. (오일러 회로)

두 정점을 제외한 모든 정점에 대해서, 나가는 간선의 수와 들어오는 간선의 수가 같다. (오일러 경로)

제외한 두 정점 중 한 정점은 나가는 간선의 수가 1 높아야하고, 나머지 한 정점은 들어오는 간선의 수가 1 높아야한다.

이 중, 나가는 간선이 1 높은 점이 오일러 경로의 시작점이 되고, 1 낮은 점이 오일러 경로의 도착점이 된다.

 

// 단방향 그래프에서 오일러 경로 또는 회로 존재여부 확인 코드

int outdegree[N]; //outdegree[i] : i번 정점에서 나가는 간선의 수
int indegree[N]; //indegree[i] : i번 정점으로 들어오는 간선의 수
int stNode; // 오일러 회로 / 경로의 시작점이 될 수 있는 정점
bool chk_Euler()
{
    int minus1 = 0;
    int plus1 = 0;
    for(int i=0;i<N;i++)
    {
        int dif = outdegree[i] - indegree[i];
        if(dif < -1 || dif > 1) return false; //간선의 차가 |1|보다 크면 오일러 없음
        if(dif == 1) 
        {
            plus1++;
            stNode = i; //나가는 간선이 1 많은 정점이 오일러 경로 출발점
        }
        if(dif == -1) minus1++;
    }
    //minus1, plus1이 둘 다 0일 경우 오일러 회로 존재, 둘 다 1일 경우 오일러 경로 존재.
    return (minus1 == 0 && plus1 == 0) || (minus1 == 1 && plus1 == 1);
}