계발자 블로그
[알고리즘] BFS(Breadth-First Search) 너비 우선 탐색 본문
BFS란?
Breadth-First Search의 줄임말로 너비 우선 탐색이라고 합니다.
그래프 탐색 알고리즘 중 하나로 루트 노드(혹은 다른 임의 노드)에서 시작해서
인접한 노드를 먼저 탐색하는 방식입니다.
두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다.
특징
- 재귀적으로 동작하지 않는다.
- 큐(Queue) 자료구조를 사용한다.
0 - 1 - 2 - 3 - 4 - 5 - 6 순으로 탐색하게 됩니다.
코드로 구현해 보기
BFS에서는 queue를 직접 생성해줍니다.
DFS에서 stack은 컴퓨터가 항상 스택의 원리를 사용하고 있기 때문에 굳이 새로운 스택을 사용하지 않아도 됬습니다.
각 노드의 레벨을 나타내기 위한 L을 만들었습니다.
성공적으로 너비 우선 탐색이 실행된 모습을 볼 수 있습니다.
'Algorithm' 카테고리의 다른 글
[알고리즘] 선택정렬 (0) | 2022.05.17 |
---|---|
[알고리즘] 에라토스테네스의 체 (0) | 2022.05.16 |
[알고리즘] DFS(Depth-First Search) 깊이 우선 탐색 (0) | 2022.04.19 |
[알고리즘] 피보나치 수열 (0) | 2022.04.09 |
[알고리즘] 재귀함수 (0) | 2022.04.08 |