[탐색알고리즘] 깊이 우선 탐색, 너비 우선 탐색

깊이 우선 탐색(depth-first search, DFS)은 부모노드부터 왼쪽부터 자식노드가 없을 때까지 탐색하고 탐색하려는 값이 없으면 루트의 다음 자식 노드를 탐색합니다.

 

• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적음
  • 목표노드가 깊은 단계에 있을 경우 탐색을 빨리 할 수 있음
• 단점
  • 탐색한 결과가 최단 경로가 된다는 보장은 없음

 

이론출처: https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

너비 우선 탐색(Breadth-first search, BFS)은 시작 노드를 탐색하고 인접한 모든 노드를 우선 탐색하는 방법입니다. 더 이상 탐색히자 않은 노드가 없을 때까지 탐색하지 않은 모든 노드들에 대해서도 너비 우선 탐색을 적용합니다.

Queue를 사용해서 레벨 순서대로 접근해야합니다.

 

• 장점
  • 출발노드에서 목표노드까지의 최단 길이 경로를 보장
• 단점
  • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간이 필요
  • 탐색하려는 값이 없다면 유한 트리에서는 모든 노드를 탐색한 후에 실패로 종료
  • 무한 트리에서는 탐색하려는 값이 없을 경우 종료되지 않음

이론출처: https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

 

깊이 우선 탐색은

인접행렬로 이차원 배열 (int[][])

인접리스트로 LinkedList[], ArrayList[]

 

넓이 우선 탐색은 Queue

 

자료구조를 사용하여 구현할 수 있습니다.

다음 포스팅에는 해당 알고리즘을 자바로 구현해보도록 하겠습니다.