[코딩테스트 알고리즘] BFS 너비 우선 탐색

개념

BFS는 그래프 탐색의 한 가지 방법

* 그래프 탐색이란?

어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법

Graph = Vertex(정점) + Edge(간선)

 

그래프 탐색 종류

- BFS : Breadth-first search(너비 우선 탐색)

- DFS : Depth-first search(깊이 우선 탐색)

 

아이디어

1. 시작점에 연결된 Vertex 찾기

2. 찾은 Vertex를 Queue에 저장

3. Queue의 가장 먼저 것 뽑아서 반복

💡 BFS - Queue / DFS - Stack

 

시간복잡도

BFS = O(V+E)

* 시간복잡도 = 알고리즘이 얼마나 오래 걸리는지

 

자료구조

- 검색할 그래프

- 방문 여부 확인(재방문 금지)

- Queue : BFS 실행

 

출처 : 개발자 장고

 

 

[정리]

BFS는 기본적으로 같은 세대에 있는 노드를 모두 탐색 후 다음 세대를 탐색

진행 중인 세대를 모두 탐색한 후 다음 세대 탐색할 수 있도록 선입선출 FIFO 자료 구조인 Queue 활용