DFS를 이용해서 사이클 탐색

  쉽게 설명하면 순환하는 정점들의 집합을 V(G)이라 할 때, 

①인접한 정점들의 간선은 그래프 내에 있어야하고,

②사이클 내에서 정점은 중복되면 안된다. 

 

 

※ 저 중에서 닫힌 보행이라는 말과 혼동하지 말라는 데, 닫힌 보행은 단순히 시작점과 끝점이 같은 경로를 말한다.

알고리즘

---

 무향 그래프와 유향 그래프 모두 DFS(깊이 우선 탐색) 알고리즘을 이용해서 탐색할 수 있다.

 - 무향 그래프 : 시간 복잡도 O(N)

 - 유향 그래프 : 강결합 요소와 위상 정렬로도 구할 수 있다.

참고 링크

---

 - http://vjerksen.tistory.com/32 (BOJ 2668 - 숫자고르기)

 - http://vjerksen.tistory.com/33 (BOJ 2526 - 싸이클)

참고 사이트

---

 - https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4%EC%82%AC%EC%A0%84 (사이클에 대한 설명)

 - https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4%EC%82%AC%EC%A0%84 (그래프 이론 용어)

※ 정확하고 부드러운 태클은 언제나 환영입니다.