[알고리즘] BFS(너비우선 탐색, 시간복잡도, 구현 방법, 특징)

특징 

큐를 사용하여서 그래프안에서 연결된 최단 거리를 찾는 알고리즘이다.

너비가 넓어지는 형태로 탐색이 진행된다.

 

 

시간복잡도

인접 리스트로 구현 되었을 경우, O(V+E)

인접 행렬인 경우, O(V^2)

 

구현 방법

큐를 이용해 조건에 만족하는 정점을 큐에 넣어서 탐색을 진행한다.

FIFO 형태로 앞 서 들어온 것을 먼저 탐색한다.