오일러 서킷
-
오일러 서킷을 찾아내는 알고리즘알고리즘 이론/알고리즘 구현 2019. 8. 28. 02:47
오일러 서킷이란? 깊이 우선 탐색을 이용해 풀 수 있는 유명한 문제로, 그래프의 모든 간성르 정확히 한 번씩 지나서 시작점으로 돌아오는 경로를 찾는 문제이다. 모든 정점이 짝수점이면서, 간선들이 하나의 컴포넌트에 포함된 그래프가 주어진다면 항상 오일러 서킷을 찾아내는 알고리즘을 만들 수 있다. findRandomCircuit(u)는 u와 인접한 간선들을 하나하나 검사하면서, 아직 방문하지 않은 간선 (u,v)가 있다면 또다시 findRandomCircuit(v)를 호출. 더이상 따라갈 간선이 없다면 재귀 호출 종료후 반환한다. 재귀 호출이 끝나고 반환할 때 경로에 추가해줌 으로서 경로의 끝점부터 역순으로 간선들이 추가된다. 코드 ( C+ + ) #include #include using namespace..