너비 우선 탐섹 (BFS)
목차
너비 우선 탐색이란?
너비 우선 탐색(Breadth-First Search, BFS)은 하나의 시작 노드(정점)를 방문한 후, 시작 노드에 인접한 모든 노드들을 우선 방문하는 방법입니다. 대략적인 탐색 방법은 다음과 같습니다.
- 루트(시작 노드)에서 시작한다.
- 자식 노드들의 위치를 저장한다.
- 저장된 위치를 기반으로 자식 노드들을 차례로 방문한다.
- 방문한 자식 노드들의 자식 노드 위치를 다시 저장한다.
- 위의 과정을 반복한다.
- 모든 노드를 방문하면 탐색을 종료한다.
즉, 방문할 수 있는 노드들을 차례로 모두 방문한 다음 자식 계층으로 넘어갑니다. 이러한 방식의 탐색을 위해서 주로 FIFO(선입선출) 방식을 가진 Queue 자료구조에 방문해야할 자식 노드들의 위치를 저장해둡니다.