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

237

7

장

그래프

➌

탐색이 각 노드에 어떻게 도달했는지 기록한다.

node_from[w]

은

src

로 역방향으로 향하는 이전 노드다.

➍

탐색을 시작하기 위해

Stack

에

src

노드를 표시하고 넣는다.

Stack

의 맨 위 노드는 다음으로 탐색할 노드를 나타

낸다.

➎

깊이 우선 탐색이 완료되지 않았다면

v

는 다음으로 탐색할 노드다.

➏

v

에 인접하고 방문 처리되지 않은 노드

w

에 대해, 탐색이

v

에서 와서

w

에 도달함을 기억한다.

➐

스택 맨 위에

w

를 넣고, 다시 방문하지 않도록 방문 처리한다.

➑

src

에서 시작된 탐색의 이전 노드

v

에 대해 기록하는 탐색의 구조를 반환한다.

[그림

7

-

5

]는 깊이 우선 탐색의 실행을 시각화한 것으로

while

루프를 돌 때마다 스택이 업데

이트된 상태를 보여준다. 스택 맨 위에 있는 음영 처리된 노드는 현재 탐색 중인 칸이고 나머지

는

미래에 처리

할 노드를 나타낸다. 그렇다면 깊이 우선 탐색은 영원히 목적 없이 방황하는 것

을 어떻게 방지할까? 노드가 스택에 들어가면 방문 처리된다는 것은 스택에 다시 들어갈 일이

없음을 의미한다.

w

에 대한

for

루프는

v

에 인접하고 방문 처리되지 않은 (아직 탐색하지 않은 )

모든 노드를 찾는다. 각

w

를 방문 처리하고 이후 탐색을 위해

w

를 스택에 넣는다.

그림

7-5

깊이 우선 탐색은 ...