DFS & BFS

Syoee·2023년 12월 11일

BFS DFS algorithm

Algorithm

목록 보기

4/6

1. DFS

1-1. DFS란?

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

1-2. 깊이 제한과 백트래킹

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

1-3. 알고리즘

만일 트리가 아닌 그래프를 탐색하게 된다면 약간의 변화가 필요하다.
우선 그래프에서의 깊이(depth)를 결정할 필요가 있다.
일반적으로 그래프에서는 루트 노드의 깊이를 0으로 하며, 임의의 노드의 깊이는 이의 부모 중 가장 깊이가 작은 것의 깊이에 1을 더한 값으로 정의한다.
따라서 그래프에서의 깊이우선탐색은 OPEN에 있는 노드 중 가장 깊은 것을 택하여 확장시키게 된다.
후계 노드가 생성되어 이 중에 이미 OPEN이나 CLOSED에 있는 것이 있다면, 깊이를 재조정하여야 한다.
여기서 알 수 있는 것은 일반적인 그래프를 탐색하는 경우라도, 탐색 과정에 의하여 얻어지는 노드들과 포인터들은 역시 탐색 트리를 형성한다는 것이다. 즉, 포인터들은 오직 하나의 부모를 가리키게 된다.

1-4. 장단점

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

1-5. 시간과 저장공간 분석

깊이 우선 탐색에서 필요로 하는 시간과 저장공간을 분석해 보면, 일반적으로는 시간에 대해 말하기가 좀 어려운데, 이는 트리가 무한할 경우, 깊이우선 탐색은 목적을 만족시키는 노드를 찾지 못할 수도 있을 뿐 아니라 알고리즘이 끝나지 않을 수도 있기 때문이다.
트리의 깊이가 목적 노드 깊이와 같을 때에는 최악의 경우 모든 노드를 다 검사하게 된다.
이 경우 전체 시간은 $1+b+b^{2}+\cdots +b^{d}={\frac {b^{{d+1}}-1}{b-1}}$ 이 된다.
깊이우선 탐색에 의해 방문된 노드수의 평균은 ${\frac {b^{{d+1}}+db+b-d-2}{2(b-1)}}$ 인데, 이것은 $d+1$ 과 ${\frac {b^{{d+1}}-1}{b-1}}$ 의 평균이며, 이 때 $d+1$ 은 목적 노드가 제일 왼쪽에 있을 때 방문하게 되는 노드의 수이고, ${\frac {b^{{d+1}}-1}{b-1}}$ 은 목적 노드가 탐색트리의 맨 오른쪽에 있을 때 방문하는 노드의 수이다.
저장공간의 사용량을 계산해 보면 좀 더 희망적인 결과를 얻을 수 있다.
탐색공간 내의 각 노드 $n$ 에서 깊이우선 탐색 알고리즘이 기억해야 할 것은 루트 노드로부터 $n$ 까지의 경로 상에 있는 각 노드의 자식들 중 $n$ 을 제외한 것들이다.
그러한 경로 중 가장 긴 경로의 길이가 $d$ 이므로, 최악의 경우 깊이우선 탐색은 $d(b-1)+1$ 에 비례하는 비교적 적은 공간을 사용한다.
연구 결과에 따르면 깊이우선 탐색은 저장공간의 사용에 있어서 점근 최적인 것으로 알려져 있다.

2. BFS

2-1. BFS란?

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.
더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

2-2. 장단점

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