BFS 알고리즘

BFS란?

Breadth-First_Search의 약자로 너비 우선 탐색 알고리즘이다. 그래프를 탐색할 때 사용되는 알고리즘이다. DFS 알고리즘처럼 그래프를 탐색하지만 탐색하는 방법이 다르다. DFS는 깊이를 우선으로 탐색하는데 BFS는 너비를 우선으로 탐색을 진행한다. 즉, 자식 노드를 탐색하기 전에 같은 레벨의 다른 노드를 탐색한다.

그럼 언제 사용함?

최단 경로, 혹은 임의의 경로를 찾을 때 사용한다 .

특징

DFS와 비교해서 설명을 해보겠다. 먼저 사용되는 자료구조에서 첫 번째 차이점이 있다. DFS에서는 stack을 사용하지만 BFS에서는 queue를 사용한다. stack은 LIFO(Last In First Out)방식으로 요소들이 관리 되고, queue는 FIFO(First In First Out)방식으로 요소들이 관리 된다.

두 번째 BFS는 재귀적으로 동작하지 않는다. (DFS는 재귀적으로 동작한다.)

세 번째 DFS는 여러 갈래 중 무한한 길이를 가지고, 목표 노드가 다른 갈래에 있는 경우 무한한 길이에 빠져들어 탐색을 할 수 없지만 BFS는 각 갈래들을 모두 탐색하면서 내려가기 때문에 탐색이 가능하다.

근데 만약 목표 노드가 가장 깊은 곳에 있다면 DFS로 탐색한 것과 차이가 없거나 더 안좋은 성능이 나온다.

동작

각 노드에 있는 수는 탐색 되는 순서이다. 1번 노드에서 부터 탐색을 시작하게 되면 2, 3, 4, … 12번 노드 순으로 탐색이 진행된다.

한 노드에 방문하게 되면 그 노드의 자식 노드들을 queue에 추가한다. 만약 stack에 저장했다면 제일 최근에 저장된 노드인 자식 노드로 이동을 하겠지만 queue에 저장했기 때문에 가장 마지막에 저장된 현재 노드의 같은 레벨에 있는 노드를 탐색하게 된다.