[알고리즘] 완전탐색 - 너비 우선 탐색(BFS)

완전탐색

임의의 정점에서 시작하여 모든 정점을 방문하는 탐색방법으로

너비 우선 탐색(BFS), 깊이 우선 탐색(DFS) 등이 있다.

 

너비 우선 탐색(BFS)

시작 정점에 인접한 정점부터 차례로 탐색하는 알고리즘 

Queue 자료구조를 사용한다.

현재 정점에서 인접한 정점을 모두 queue에 저장하고 

순서대로 모두 방문하고 저장하는 과정을 반복하여 모든 정점을 방문한다.

방문한 정점은 따로 체크를 해두어서 중복방문을 막아야한다.

 

사용 조건

1. 최소비용, 최단거리 문제

2. 간선의 가중치가 1이어야 한다.

 

시간 복잡도

- 인접 행렬: O(V²)

- 인접 리스트: O(V+E)

 

V: 간선의 개수

E: 정점의 개수