깊이 우선 탐색(DFS : Depth First Search)

깊이 우선 탐색(Depth First Search)은 DFS라고도 불리며 그래프를 순회하는 방법 중에 하나이다. 깊이 우선 탐색은 한 정점을 기준으로 인접한 정점을 방문한 뒤 방문한 정점을 기준으로 다시 인접한 정점을 방문하는 방식의 재귀적인 방법으로 방문을 한다. 깊이 우선 탐색은 다음과 같은 방법으로 진행된다.

1. 깊이 우선 탐색을 시작할 정점을 선택한다.
2. 선택된 정점을 방문 처리한다.
3. 정점 v에 인접한 정점들에 대해
   3-1. 방문되지 않은 정점이 존재하면 정점 v를 스택에 push하고, v의 인접 정점들 가운데 방문되지 않은 정점 w를 선택하여 2의 과정부터 다시 시작한다.
   3-2. 방문되지 않은 정점이 존재하지 않는다면 가장 최근에 스택에 push된 정점을 pop하여 3의 과정부터 다시 사작한다.
4. stack이 빌 때까지 2, 3과정을 반복한다.

 

깊이 우선 탐색은 스택이나 재귀 함수를 통해 구현할 수 있다. 일반적으로 재귀 함수를 많이 사용한다. 하지만 재귀 함수도 시스템적으로는 스택을 사용하기 때문에 결국 스택의 형태로 구현된다. 다음은 깊이 우선 탐색의 예시이다.

 

정점 0 방문

처음에 방문할 정점을 정한다. 이번 예시에서는 정점 0을 방문한다. 그리고 방문함과 동시에 스택에 넣어준다.

 

정점 1 방문

정점 1을 방문한 후 스택에 넣어준다.

 

정점 2 방문

정점 2를 방문한 후 스택에 넣어준다.

정점 4 방문

정점 4를 방문하기 전에 정점 2에서는 더 이상 인접한 정점에 방문할 수 없다. 그러면 스택에서 pop을 한다. 이전 스택에서 pop을 하면 1이 가장 위에 올라오고 그러면 1와 연결된 정점인 4를 방문할 수 있다. 방문하면서 4를 스택에 넣어준다.

 

 

정점 3 방문

정점 3를 방문하고 스택에 넣어준다.

정점 5 방문

정점 5을 방문하고 스택에 넣어준다.

 

 

정점 6 방문

정점 6을 방문하고 스택에 넣어준다.

깊이 우선 탐색 종료

모든 정점을 방문했기 때문에 깊이 우선 탐색은 종료된다. 종료될 때는 앞서 2번에서 4번 정점을 방문할 때 스택에서 없어지는 것처럼 이제 더 이상 방문할 정점이 없기 때문에 스택에서는 자동적으로 함수가 종료됨과 동시에 스택은 비워지게 된다.