[그래프 알고리즘]오일러 경로/회로 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 큰 노드가 끝 노드입니다.

구현

인접리스트로 구현