너비 우선 탐색 (BFS : Breadth-First Search)

너비 우선 탐색 BFS는 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.

 

기능	특징	시간 복잡도 (노드 수 : V, 에지 수: E)
그래프 완전 탐색	FIFO 탐색 Queue 자료구조 이용	O(V+E)

 

 

너비 우선 탐색의 핵심 이론

1. BFS를 시작할 노드를 정한 후 사용할 자료 구조 초기화하기

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입하기

3. 큐 자료구조에 값이 없을 때까지 반복하기