BFS(Breadth-first search)
너비 우선 탐색이란 뜻으로 맹목적 탐색 방법의 하나로 시작 노드(정점)를 방문한 후 시작 노드에 인접한 모든 노드들을 우선 방문하는 알고리즘 더 이상 방문하지 않은 노드가 없을 때까지 방문하지 않은 모든 노드들에 대해서도 너비 우선 탐색을 적용한다. (BFS는 큐 자료구조를 이용)
맹목적 탐색(Blind search) : 문제의 상태 공간 정보를 이용하지 않고 정해진 순서에 따라 공간 그래프를 점차 생성해 가면서 해를 찾는 방법 (문제 정보를 이용하는 정보이용 탐색과 달리 비효율적이고 시간이 오래 걸린다.
노드 : 컴퓨터 과학에 쓰이는 기초적인 단위로 대형 네트워크에서는 장치나 데이터 지점을 의미한다. 노드는 하나의 자료 구조에 포함된 정보를 표현한다.
BFS의 장단점
장점
- 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
단점
- 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 메모리 공간을 필요로 하게 된다.
- 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
- 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.
BFS의 시간 복잡도
- 인접 리스트 : (정점의 개수: V, 간선의 개수: E)
- 인접 행렬 : (정점의 개수: V)
DFS(Depth-first search)
깊이 우선 탐색이란 뜻으로 맹목적 탐색 방법의 하나로 루트 노드(혹은 다른 임의의 노드)에서 시작해 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 알고리즘이다. 즉, 그래프에서 깊은 부분을 우선적으로 탐색한다. (DFS는 스택 자료구조 혹은 재귀 함수를 이용)
깊이 제한과 백트래킹
탐색 과정이 시작 노드에서 한없이 깊이 진행되는 것을 막기 위해 깊이 제한(depth bound)을 사용한다. 깊이 제한에 도달할 때까지 목표노드가 발견되지 않으면 최근에 첨가된 노드의 부모노드로 되돌아와서, 부모노드에 이전과는 다른 동작자를 적용하여 새로운 자식노드를 생성한다. 여기서 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라고 한다.
DFS의 장단점
장점
- 단지 현 경로상의 노드들만을 기억하면 되므로 저장공간의 수요가 비교적 적다.
- 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.
단점
- 해가 없는 경로에 깊이 빠질 가능성이 있다. 따라서 실제의 경우 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음의 경로를 따라 탐색하는 방법이 유용하다.
- 얻어진 해가 최단 경로가 된다는 보장이 없다. 이는 목표에 이르는 경로가 다수인 문제에 대해 깊이 우선 탐색은 해에 다다르면 탐색을 끝내버리므로, 이때 얻어진 해는 최적이 아닐 수 있다는 의미이다.
DFS의 시간 복잡도
- 인접 리스트 : (정점의 개수: V, 간선의 개수: E)
- 인접 행렬 : (정점의 개수: V)
Reference
Whatever does not destroy me makes me stronger.