깊이 우선 탐색(DFS)

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

 : 루트 노드(혹은 임의의 노드)에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

 

깊이 우선 탐색(DFS)의 특징

• 자기 자신을 호출하는 순환 알고리즘의 형태
• 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류.
• 어떤 노드를 방문했는지 여부를 반드시 검사해야함.

 

깊이 우선 탐색(DFS)의 과정

1. x노드(시작 노드)를 방문.

• 방문한 노드를 표시

2. x노드와 인접한 노드 중 방문하지 않은 노드 차례대로 순회.

• if) 인접한 노드가 없다면 -> 종료

3. 방문하지 않은 노드가 없다면, 이전 정점으로 역추적(backtracking).

 

4. 모든 노드를 방문할 때 까지 반복.

 

 

깊이 우선 탐색(DFS)의 구현

 

- Stack 활용

1. 임의의 노드에서 시작하여 방문한 것으로 표시하고, 스택에 push

2. 스택에서 맨 위의 노드를 가져옴.

3. 방문하지 않은 인접 노드를 방문 및 표시하고, 스택에 push

4. 스택이 비워질 때까지 반복.