DFS (1) - DFS (Depth-First Search) 란?

DFS (Depth-First Search)란 깊이 우선 탐색의 약자로 그래프의 탐색(traversal, 순회) 방법 중 하나이다. 이 탐색 알고리즘은 말그대로 특정한 경로로 노드를 탐색하다가 가장 깊은 곳까지 탐색하고 경로를 다시 돌아가 다른 경로로 탐색하는 방식을 보인다. 구체적인 DFS의 동작 과정은 아래와 같다.

DFS의 동작과정
 
  1. 탐색을 시작하는 노드를 스택에 삽입하고 방문 처리한다.

  2. 스택의 최상단 노드에 인접한 노드가 있을 때 아래와 같은 경우에 나누어서 처리한다.
    2-1. 인접 노드 중 방문하지 않은 노드가 존재할 때, 그 노드를 방문하고 스택에 삽입, 방문 처리한다.
    2-2. 인접 노드 중 방문하지 않은 노드가 존재하지 않을 때, 스택의 최상단 노드를 꺼낸다.

  3. 과정2를 더 이상 수행할 수 없을 때까지 반복한다.

해당 그래프에서 V0를 탐색 노드로 설정하고 DFS를 진행해보자. 

탐색 순서는 다음과 같을 것이다. 0 -> 1 -> 3 -> 7 -> 4 -> 5 -> 2 -> 6

스택에 들어가는 과정은 다음과 같을 것이다.

---

스택과 재귀 함수에 관한 게시물을 통해서 재귀 함수를 통해 쉽게 스택을 구현할 수 있음을 알게 되었다. 따라서 DFS는 재귀 함수로 구현하며 이로써 스택의 기능을 겸비할 수 있게 구현해야 한다. 재귀 함수로 구현한 DFS의 소스코드는 아래와 같다.