11.사이클 탐지

Q.  그래프에서 사이클 탐지(Cycle Detection) 방법 중 깊이 우선 탐색(DFS) 기반 방법은 무엇인가요

 

DFS를 활용한 사이클 탐지 방법은 노드를 방문할 때마다 해당 노드의 상태를 추적하는 방식입니다. 탐색 중에 이미 방문한 노드가 현재 경로에 포함되어 있으면 사이클이 있다고 판단합니다. 보통 그래프를 재귀적으로 탐색하여 이러한 사이클을 발견합니다

 

관련 개념:

DFS(Depth First Search): 그래프의 노드를 깊이 우선으로 탐색하는 방법입니다.

Back Edge(백 엣지): DFS 탐색 중 현재 경로에 있는 노드로 연결된 간선을 의미합니다.
Visited Status(방문 상태): 노드의 방문 여부를 기록하여 사이클을 찾아내는 방식입니다