깊이 우선 탐색은 앞선 너비 우선 탐색과는 달리 Root Node부터 시작하여 가장 깊은 곳까지 탐색한 후 돌아서 모든 정점을 방문하는 방법이다.
위의 그림과 같이 깊이 우선 탐색에서는 한 쪽 노드를 선택하면 그 노드로부터의 가장 깊은 곳까지 탐색한 후 동일 높이의 노드를 탐색한다.
구현
DFS를 구현하기 위해서는 후입선출의 자료구조인 스택을 이용한다.
기본 원리는 정점을 처음 방문할 때 스택에 삽입하고, 해당 스택에서 방문할 수 있는 vertex를 탐색하며 방문한 다음에, 방문할 수 있는 vertex가 더이상 존재하지 않을 때 스택에서 제거해주는 것이다.
구현에서는 스택 자료구조를 직접 이용해줄 수도 있고, 재귀 호출을 통해 스택을 간접적으로 사용해줄 수도 있다.
특징
BFS에 비해 저장공간의 필요성이 적고, 찾아야 할 노드가 깊은 단계에 있을 수록 유리하다.
DFS(깊이 우선 탐색), Depth-First Search
깊이 우선 탐색은 앞선 너비 우선 탐색과는 달리 Root Node부터 시작하여 가장 깊은 곳까지 탐색한 후 돌아서 모든 정점을 방문하는 방법이다.
위의 그림과 같이 깊이 우선 탐색에서는 한 쪽 노드를 선택하면 그 노드로부터의 가장 깊은 곳까지 탐색한 후 동일 높이의 노드를 탐색한다.
구현 DFS를 구현하기 위해서는 후입선출의 자료구조인 스택을 이용한다. 기본 원리는 정점을 처음 방문할 때 스택에 삽입하고, 해당 스택에서 방문할 수 있는 vertex를 탐색하며 방문한 다음에, 방문할 수 있는 vertex가 더이상 존재하지 않을 때 스택에서 제거해주는 것이다.
구현에서는 스택 자료구조를 직접 이용해줄 수도 있고, 재귀 호출을 통해 스택을 간접적으로 사용해줄 수도 있다.
특징 BFS에 비해 저장공간의 필요성이 적고, 찾아야 할 노드가 깊은 단계에 있을 수록 유리하다.