깊이 우선 탐색

깊이 우선 탐색(DFS)은 맹목적 탐색 방법의 하나.
탐색 트리의 최근에 추가된 노드를 선택하고, 노드에 적용 가능한 동작 방법 중 하나를 적용하여 트리에 다음 레벨의 한 개의 자식노드를 추가하여, 추가된 자식 노드가 목표 노드일 때 까지 앞의 자식 노드 추가 과정을 반복해 가는 방식이다.

탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한을 사용한다. 깊이 제한에 도달할 때 까지 목표노드가 발견되지 않으면 최근에 추가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작 방법을 적용하여 새로운 자식노드를 생성한다.

깊이 우선 탐색의 장점으로

• 현 경로상의 노드들만 기억하면 되므로 저장공간의 수요가 비교적 적다.
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

깊이 우선 탐색의 단점으로

• 해가 없는 경로에 깊이 빠질 가능성이 있다.
• 얻어진 해가 최단 경로가 된다는 보장이 없다.

너비 우선 탐색

너비 우선 탐색(BFS)는 맹목적 탐색 방법의 하나.
시작 노드를 방문한 후 시작 노드에 인접한 모든 노드들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때 까지 방문하지 않은 모든 노드들에 대해서도 너비 우선 탐색을 적용한다.

너비 우선 탐색의 장점으로

• 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장한다.
  너비 우선 탐색의 단점으로
• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.