[자료구조] 깊이 우선 탐색 / 너비 우선 탐색

깊이 우선 탐색(Depth First Search)

• 맹목적 탐색방법의 하나로 탐색을 함에 있어서 보다 깊은 것을 우선적으로 하여 탐색하는 알고리즘
• 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표노드일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식

이미지 출처 : Wikipedia

1. 탐색시작 노드를 스택에 삽입하고 방문처리함
2. 스택의 최상단 노드에게 방문하지 않은 인접노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리함 / 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2를 더이상 수행할 수 없을 때까지 반복

• 스택 자료구조에 기초함
• 빠르게 모든 경우의 수를 탐색하고자 할 때 쉽게 사용할 수 있음
• 탐색 시 O(N)의 시간이 소요됨
• 장점
  • 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
  • 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
• 단점
  • 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용할 수 있다.
  • 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.

 

너비 우선 탐색(Breadth First Search)

• 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법
• 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용

이미지 출처 : Wikipedia

1. 탐색 시작 노드를 큐에 삽입하고 방문처리 함
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입, 방문처리
3. 2번 과정을 더이상 수행할 수 없을 때까지 반복

 

• 큐 자료구조에 기초함
• 고급 그래프 탐색 알고리즘에서 자주 활용되며 O(N)의 시간 소요
• 일반적인경우 실제 수행시간이 깊이 우선 탐색보다 좋은 편

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수