[알고리즘] BFS(Breadth-First Search) 너비 우선 탐색

BFS란?

Breadth-First Search의 줄임말로 너비 우선 탐색이라고 합니다.

그래프 탐색 알고리즘 중 하나로 루트 노드(혹은 다른 임의 노드)에서 시작해서

인접한 노드를 먼저 탐색하는 방식입니다.

두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다.

 

특징

• 재귀적으로 동작하지 않는다.
• 큐(Queue) 자료구조를 사용한다.

출처 하나몬

0 - 1 - 2 - 3 - 4 - 5 - 6 순으로 탐색하게 됩니다.

 

코드로 구현해 보기

BFS에서는 queue를 직접 생성해줍니다.

DFS에서 stack은 컴퓨터가 항상  스택의 원리를 사용하고 있기 때문에 굳이 새로운 스택을 사용하지 않아도 됬습니다.

각 노드의 레벨을 나타내기 위한 L을 만들었습니다.

 

성공적으로 너비 우선 탐색이 실행된 모습을 볼 수 있습니다.