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

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

 - 탐색을 함에 있어서 보다 깊은 것을 우선적으로 탐색하는 것이다.

 - 너비 우선 탐색에서는 큐가 사용되었다면 깊이 우선 탐색은 스택을 사용한다.

 

▼그림을 참고하자.

 

▼스택을 이용하여 노드를 담는다.

 

▼5번 노드까지 담고 3번 노드를 담기 위하여 다시 2번 노드까지 마지막에 담긴 순서대로 뺀다.

그렇게 1번 노드가 담긴 상태에서 3번 노드를 넣는다.

 

그림 순서대로와 같이 마지막에 선택된 노드의 인접한 방문하지 않은 노드를 방문한다.

방문하지 않은 노드가 없을 시 모든 노드를 스택에서 제거한다.

방문순서는 1-2-4-5-3-6이 된다.