알고리즘 공부<10> 깊이 우선탐색

지난번에는 너비 우선 탐색에 대해서 공부하였다. 이번에는 이와 비슷하면서도 다른 깊이 우선 탐색 알고리즘에 대해서 알아보자.

1. 깊이 우선 탐색

Search as deep as possible first

가능한한 깊게 찾아라라는 의미로 깊이 우선 탐색의 핵심을 의미한다고 볼 수 있다. 

가장 최근에 발견되어진 꼭지점 V에서 시작하는 간선을 찾으며 끝까지 찾았을 때 이후 다시 뒤로 돌아가며 남은 꼭지점이 있는지 찾게 된다. 이후 있다면 다시 그 꼭지점으로부터 시작되는 모든 간선을 찾게 된다. 이와 같은 과정을 모든 꼭지점을 찾을 때 까지 계속 되어진다.

잘 이해가 안되겠지만 의사코를 한번 살펴보면 이해가 될것이다. 사전에 먼저 정의를 하자

자 이와 같다고 할때

1 ~ 4 먼저 각 노드에 대해서 (v개의 노드) 초기화 과정을 거친다. => 빅오 O(V)

5 번 이후 부터가 이제 탐색하게 된다.

이후 각 노드에 대해서  ( V개의 노드)  깊이 우선 탐색을 실시하게 된다.

노드의 색이 하얀색일 경우 즉 발견되지 않았을 경우 탐색이 수행되어진다.

발견되었으므로 Gray색으로 바꿔주며 현재 시간에 경과된 시간을 더해준후 해당 노드의 발견시간(d[u])에 넣어준다.

4 ~ 7 그리고 노드에 인접하는 노드 즉 인접하는 간선의 개수 만큼 아래 과정이 수행 되어진다.

인접하는 노드(v)가 하얀색 일 경우 그 노드의 predecessor를 u를 넣어주고 ( u - v)  노드 v에 대하여 위의  깊이 우선 탐색을  재귀적으로 수행하게 된다.

이후 각 노드별로 전부 수행되어지고 

8 ~ 9더이상 이어진 노드가 없을 때  검정색으로 바꿔주고 경과되시간을 한번 더 해준후 리턴하게 된다  이후 역시 재귀적으로 호출한 순서에 역순으로 리턴해가며 검정색으로 바꿔주게 된다.  

이러한 과정은 각노드에 대한 차수만큼 수행되어지므로 (무방향그래프는 차수/2)  총 간선의 개수만큼 수행되어진다. 즉 빅오 O(E)가 된다.

따라서 총 수행시간은 O(V+E) 가 된다.

오늘은 간단하게 이 정도만 하고 다음에는 그래프 관련 새로운 공부를 시작하겠습니다.