DFS(Depth-First Search)

DFS(Depth-First Search)

 

깊이 우선 탐색.

 

이름 그대로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘을 말한다.

 

정확하게는 DFS는 깊은 부분을 끝까지 탐색하다가,

막히면 다시 돌아와서, 다른 부분을 깊게 탐색한다.

 

직접 그려본 DFS

 

DFS의 탐색 순서

 

DFS는 A에서 출발해서 B를 선택하여 탐색을 시작하고, B에서 이미 A는 탐색했으니, D로 넘어간다.

그리고 D에서는 이미 B를 탐색했으니, H로 넘어가게 되고, 이제 더 이상 방문할 인접 노드가 없는 H에서는

자신의 앞전 노드인 D로 돌아가고, 방문할 수 있는 노드인 I로 이동한다.

그리고 I는 거꾸로 D로 돌아가고, 이제 더 이상 방문할 노드가 없으니, B로, 그 다음은 A로 거슬러 올라간다.

그리고 A에서는 이제 반대편 노드를 탐색하기 시작하는 것이다.

 

그리고 마지막 G까지 탐색하면, 모든 노드의 탐색이 끝나는 것이다.

 

DFS의 구현

 

DFS를 구현하기 위해서는 스택 혹은 재귀함수를 이용한다.

 

DFS에서는 노드가 더 방문할 노드가 없는 경우, 자신의 앞전 노드로 돌아가게 된다.

 

이것을 구현하기 위해서는,

 

스택에서는 방문하는 순서대로 노드를 스택에 쌓고, 방문이 끝나면 Pop 연산을 사용해서 구현이 가능하다.

또한 재귀함수 역시 스택 메모리 공간에 쌓아올려지는 구조를 가지므로, 재귀함수를 사용하여도 구현이 가능하다.