똑똑한 코드 작성을 위한 실전 알고리즘

252

똑똑한 코드 작성을 위한 실전 알고리즘

return True

in_stack[v] = False

➏

return False

for v in DG.nodes():

➐

if not v in marked:

if dfs(v):

➑

return True

return False

➊

v

에서 시작해 그래프

DG

에 깊이 우선 탐색을 수행한다.

➋

in_stack

은 재귀 호출 스택 내에 있는 노드를 기록한다.

v

를 표시하면 이제 재귀 호출의 일부에 있다는 의미다.

➌

marked

사전 타입 변수는 이미 방문한 노드를 기록한다.

➍

v

와 인접한 각 방문 처리되지 않은 노드

w

에 대해

w

로 재귀

dfs()

를 시작하고,

True

가 반환되면 순환이 검출되었다

는 의미이므로 해당 함수는

True

를 반환한다.

➎

노드

w

가 방문 처리되었다면 여전히 호출 스택 내에 있으며 순환이 검출되었다는 의미다.

➏

dfs()

의 재귀 호출이 끝날 때,

v

가 더는 호출 스택에 있지 않으므로

in_stack[v]

를

False

로 설정하는 것도 중요

하다.

➐

유향 그래프에서 방문 처리되지 않은 노드를 각각 조사한다.

➑

노드

v

에

dfs(v)

를 수행해 순환이 검출되면 즉시

True

를 반환한다.

dfs

()

가 재귀 호출을 수행함에 따라 결국 각 노드가 간선이 없더라도 방문 처리될 때까지 계

속해서 그래프를