BFS(Breath First Search) #

BFS(Breath First Search, 너비우선탐색)는 DFS(Depth First Search) 와 더불어 Tree를 조사하는 가장 기본적인 알고리즘 중 하나로 Root Node를 중심으로 Depth를 하나씩 늘려가며 전수조사를 수행하는 알고리즘이다. BFS는 Stack을 사용하는 DFS와 달리 Queue를 이용하며, 무한대의 크기의 Depth를 가지는 Tree가 있을 때 찾고자하는 Node가 Tree안에 있다면 이론적으로 언젠가는 사용자가 원하는 Node를 찾을 수 있다는 것을 보장한다. (DFS는 이를 보장 할 수 없다)

BFS 알고리즘 #

BFS의 알고리즘은 Queue를 활용하여 구현한다. 기본 원리는 아래와 같다.

1. Queue에 최상위 노드(Root Node)를 넣는다.
2. Queue에서 노드 하나를 Pop()한다.
3. Queue에서 Pop한 노드의 자식노드들을 전부 Queue에 넣는다.
4. Queue에 더이상 Pop()가능한 Node가 없을때까지 이 작업을 반복한다.

위 그림에서와 같이 맨처음에 Root Node인 0 노드를 큐에 삽입한다, 그 이후 큐에서 하나의 값(0번 노드)을 Pop 하고 Pop한 노드의 자식 노드들을 다시 큐에 집어넣는다. 위와 같은 검색 방식은 노드들을 Depth가 가까운것부터 검색하며, 모든 노드들을 순차적으로 훑어 나아간다.

BFS vs DFS #

그렇다면 BFS(너비우선탐색)과 DFS(깊이 우선탐색)은 언제 쓰는것이 옳을까? BFS와 DFS모두 Time Complexity는 O(N)으로 같으나, Space Complexity는 DFS 의 경우 Tree의 최대 깊이( O(log(N)) ), BFS의 경우 큐에 쌓이는 용량 O(logN)만큼의 공간복잡도를 활용하므로 DFS가 좀더 유리하다. 하지만, DFS는 웹페이지, SNS의 연결망 같은 무한대에 가까운 깊이를 가지는 Tree(혹은 Graph)의 경우 정답이 되는 Path를 찾아가지 못하는 경우에는 정답을 찾을 수 있다는 보장을 할 수 없다. 이러한 경우에는 컴퓨터의 자원만 보장된다면, 얼마의 시간이 걸릴지는 모르지만 BFS를 이용해 정답을 찾을 수 있다.

Incoming Links #

Related Data Sciences (DataScience 0) #

• DFS