[그래프 알고리즘]오일러 경로/회로 Eulerian Path/Circuit(방향 그래프)

2022.07.12 - [알고리즘] - 오일러 경로/회로 Eulerian path/circuit(무향그래프)

오일러 경로/회로 Eulerian path/circuit(무향그래프)

 

방향 그래프에서의 오일러 경로를 구하는 것은 무향 그래프에서의 오일러 경로를 구하는 것과 크게 다르지 않습니다.

오일러 경로의 존재성

방향 그래프에서의 한 노드로 들어오는 엣지의 개수를 in_degree, 나가는 엣지의 개수를 out_degree라고 한다면,

다음 두 조건중 하나를 만족해야 오일러 경로가 존재합니다.

1. 각 노드의 in_degree와 out_degree가 같다.
2. 한 노드에서 in_degree는 out_degree보다 1 크고, 어떤 노드에서는 out_degree가 in_degree보다 1 크고, 나머지 노드에서는 in_degree와 out_degree가 같다.

2번 조건을 만족하는 경우 out_degree가 1 큰 노드가 시작노드, in_degree가 1 큰 노드가 끝 노드입니다.

구현

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	#define N_NODE 7
	#define INF 9999999
	int adjMat[N_NODE][N_NODE];
	int in_degree[N_NODE], out_degree[N_NODE];
	void addEdge(int u, int v){
	adjMat[u][v]++;
	out_degree[u]++;
	in_degree[v]++;
	}
	vector<int> path;
	void eulerPath(int here){
	for(int there=0;there < N_NODE; there++){
	while(adjMat[here][there]){
	// 이동하기 전 엣지 지우기
	adjMat[here][there]--;
	eulerPath(there);
	}
	}
	// 마지막에 here를 경로에 추가한다.
	path.push_back(here);
	}
	int main(){
	// 그래프 생성
	addEdge(0, 1);
	addEdge(1, 3);
	addEdge(3, 5);
	addEdge(5, 3);
	addEdge(3, 4);
	addEdge(4, 5);
	addEdge(5, 1);
	addEdge(1, 2);
	addEdge(2, 0);
	addEdge(2, 5);
	int start = 0;
	// out_degree가 1 큰 노드를 시작노드로 고르기, 없으면 0
	for(int i=0;i<N_NODE;i++){
	if(out_degree[i] == in_degree[i] + 1) {
	start = i;
	}
	}
	eulerPath(start);
	// 역순으로 저장되어 있으므로 뒤집는다.
	reverse(path.begin(), path.end());
	for(int node : path){
	cout << node << " ";
	}
	return 0;
	}

view raw euler_path_directed.cpp hosted with ❤ by GitHub

인접리스트로 구현

	#include <iostream>
	#include <vector>
	#include <algorithm>
	using namespace std;
	#define N_NODE 7
	#define INF 9999999
	struct Edge {
	// 엣지의 활성화 여부
	bool isActive = true;
	int dst;
	Edge(int dst){
	this->dst = dst;
	}
	};
	vector<Edge*> adjList[N_NODE];
	void addEdge(int u, int v){
	Edge *utov = new Edge(v);
	adjList[u].push_back(utov);
	}
	vector<int> path;
	void eulerPath(int here){
	for(Edge *there : adjList[here]){
	// 만약 엣지가 활성화되어 있으면 이동한다.
	if(there->isActive) {
	// 이동한 엣지를 비활성화 한다.
	there->isActive = false;
	eulerPath(there->dst);
	}
	}
	// 마지막에 here를 경로에 추가한다.
	path.push_back(here);
	}
	int main(){
	// 그래프 생성
	addEdge(0, 1);
	addEdge(1, 3);
	addEdge(3, 5);
	addEdge(5, 3);
	addEdge(3, 4);
	addEdge(4, 5);
	addEdge(5, 1);
	addEdge(1, 2);
	addEdge(2, 0);
	eulerPath(0);
	// 역순으로 저장되어 있으므로 뒤집는다.
	reverse(path.begin(), path.end());
	for(int node : path){
	cout << node << " ";
	}
	return 0;
	}

view raw euler_path_directed_adjlist.cpp hosted with ❤ by GitHub