오일러 경로는 연결된 그래프에서 모든 엣지를 한번씩만 지나가는 경로를 말합니다.
오일러 회로는 오일러 경로의 특수한 경우로 시작 노드와 끝노드가 같습니다.
오일러 경로의 존재성
무향 그래프에서 노드의 차수(degree)란 노드에 연결되어있는 엣지의 수를 말합니다.
오일러 경로의 존재성은 다음 두 조건중 하나를 만족하면 됩니다.
- 모든 노드의 차수가 짝수이다.
- 두 노드의 차수가 홀수이고, 나머지 노드는 모두 차수가 짝수이다.
2번 조건을 만족하는 경우 차수가 홀수인 두 노드가 오일러 경로의 시작 노드와 끝 노드가 됩니다.
오일러 경로 구하기
무향그래프에서 오일러 경로가 존재함을 확인한 경우, DFS를 이용해 오일러 경로를 구할 수 있습니다.
경로를 담을 비어있는 리스트를 준비합니다.
시작 노드를 정하고 DFS를 하면서 연결된 다른 노드로 이동합니다. 이동하기 전에 그 노드와의 엣지는 지웁니다.
다른 노드를 모두 방문했으면, 마지막에 현재 노드를 경로에 넣습니다.
구현
모든 노드의 차수가 짝수인 경우는 오일러 회로가 구해지게 됩니다.
인접 리스트로 구현
'알고리즘 > 그래프' 카테고리의 다른 글
| [그래프 알고리즘]해밀토니안 회로 Hamiltonian circuit (0) | 2022.07.12 |
|---|---|
| [그래프 알고리즘]오일러 경로/회로 Eulerian Path/Circuit(방향 그래프) (0) | 2022.07.12 |
| [그래프 알고리즘]kosaraju 알고리즘(SCC) (0) | 2022.07.11 |
| [그래프 알고리즘]Tarjan 알고리즘(SCC) (0) | 2022.07.11 |
| [그래프 알고리즘]boruvka 알고리즘(MST) (0) | 2022.07.11 |