한 붓 그리기가 가능하기 위해서는
정점(vertex)의 차수(degree)가 모두 짝수이거나 , 혹은 홀수 인 것이 두 개이면 가능.
정점의 차수가 모두 짝수이면 모든 간선을 한 번 방문하고 시작 위치로 돌아올 수 있고, 홀수 인것이
두 개 있으면 현 위치로 돌아올 수는 없지만 모든 간선을 한 번 방문할 수 있음. 이 경우는 홀수 인 정점에서
시작 해야 함.
구현
간선(edge)을 기준으로 dfs 하면 됨. 단 , 들어가면서 갈 수 있는 간선의 길을 없앤 후 이상 갈수 없는 경우 출력
예.
모든 정점의 차수가 짝수이므로 오일러 투어가 가능하고 , 시작 정점은 정점 중 아무 것이나
가능.
-시작 정점을 1 번 정점으로 한다면 ,
스택의 상태: 1
-2 번 정점으로 가는 간선이 유효한 간선이므로 2 번 정점으로
스택의 상태: 1 2
-3 번 정점으로 가는 간선이 유효한 간선이므로 3 번 정점으로
스택의 상태: 1 2 3
-4 번 정점으로 가는 간선이 유효한 간선이므로 4 번 정점으로
스택의 상태: 1 2 3 4
-1 번 정점으로 가는 간선이 유효한 간선이므로 1 번 정점으로
스택의 상태: 1 2 3 4 1
- 1 번 정점에서 갈수 있는 간선이 없으므로 1 번 pop ---------------------- 1
- 4 번 정점에서 갈수 있는 간선이 없으므로 4 번 pop----------------------- 4
- 3 번 정점에서 5 번 정점으로 갈수 있으므로 5 번 정점으로
스택의 상태: 1 2 3 5
- 6 번 정점으로 갈수 있으므로 6 번 정점으로
스택의 상태: 1 2 3 5 6
- 7 번 정점으로 갈수 있으므로 7 번 정점으로
스택의 상태: 1 2 3 5 6 7
- 3 번 정점으로 갈수 있으므로 3 번 정점으로
스택의 상태: 1 2 3 5 6 7 3
- 3 번 정점에서 갈수 있는 간선이 없으므로 3 번 pop ------------------------ 3
- 7 번 정점에서 갈수 있는 간선이 없으므로 7 번 pop ------------------------ 7
- 6 번 정점에서 갈수 있는 간선이 없으므로 6 번 pop ------------------------ 6
- 5 번 정점에서 갈수 있는 간선이 없으므로 5 번 pop ------------------------ 5
- 3 번 정점에서 갈수 있는 간선이 없으므로 3 번 pop ------------------------ 3
- 2 번 정점에서 갈수 있는 간선이 없으므로 2 번 pop ------------------------ 2
- 1 번 정점에서 갈수 있는 간선이 없으므로 1 번 pop ------------------------ 1
euler tour: 1 4 3 7 6 5 3 2 1