그래프 내부에 사이클이 생기면 어떻게 조건을 끝내나요?

21.01.29 17:18 작성 조회수 123

1->2->3->4 까지 가고 4->5로 가는 간선이 없다고 가정했을때

dfs(4)에서 함수가 끝나지 않을 것 같은데..

이런 조건은 어떻게 처리해야 하는지 궁금합니다!

it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비

64. 경로탐색 (그래프 DFS : Depth First Search)

강의실 바로가기

답변 1

답변을 작성해보세요.

김태원

2021.01.30

안녕하세요^^

그래프 내부에 사이클이 생겨도 노드의 방분여부를 체크하고 탐색하기 때문에 무한반복은 없을 것 같습니다.

위에 가정은 뭔지 제가 잘 모르겠습니다. 본인이 생각하는 끝나지 않을 것 같은 그래프 예를 제가 드린 소스코드로 dfs(4)가 끝나는지 끝나지 않는지 직접해보세요.