[알고리즘] 깊이 우선 탐색(DFS)

그래프의 탐색

하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 특정한 정점에서 다른 정점으로 갈 수 있는지 없는 지를 탐색을 통하여 알 수 있다.

 

깊이 우선 탐색이란?

트리에서 생각하면 이해하기가 쉽다.

자기 자신을 호출하는 순환 알고리즘의 형태 를 가지고 있다.
전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류이다.

1. a 노드(시작 노드)를 방문
- 방문한 노드는 방문했다고 표시
2. a와 인접한 노드들을 차례로 순회
- a와 인접한 노드가 없다면 종료
3. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문
- b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문
4. b의 분기를 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾음
= b의 분기를 전부  탐색한 후 a의 다른 이웃 노드를 방문할 수 있다는 뜻
- 아직 방문이 안 된 정점이 없으면 종료한다.
- 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

 

깊이 우선 탐색의 구현

구현하는 데는 2가지의 방법이 있다. 1. 순환 호출 이용2. 명시적 스택 사용 : 인접 정점들을 스택에 저장했다가 다시 꺼내 작업하는 것