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

프로그래밍/Algorithm

Baesj 2021. 8. 18. 16:12

너비 우선 탐색은 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다.

1. a에서 갈 수 있는 곳 b, c를 방문

2. b에서 갈 수 있는 곳 d, e를 방문

3. c에서 갈 수 있는 곳 f, g를 방문

4. e에서 갈 수 있는 곳 h를 방문

이런 식으로 인접한 모든 정점을 우선 방문하는 알고리즘이다.

구현 할 때는 큐(Queue)를 사용한다

1. a에서 갈 수 있는 곳 b, c를 큐에 넣고

2. 큐에서 b를 빼서 갈 수 있는 곳 d, e를 큐에 넣고

3. 큐에서 c를 빼서 갈 수 있는 곳 f, g를 큐에 넣고

4. 큐에서 d를 빼서 갈 수 있는 곳을 넣어야 하는데 없으니깐 넘어감

5. 큐에서 e를 빼서 갈 수 있는 곳 h를 큐에 넣고

6. 큐에서 f를 빼서 갈 수 있는 곳을 넣어야 하는데 없으니깐 넘어감

7. 큐에서 g를 빼서 갈 수 있는 곳을 넣어야 하는데 없으니깐 넘어감

8. 큐에서 h를 빼서 갈 수 있는 곳을 넣어야 하는데 없으니깐 넘어감

큐가 비어 질때까지 수행한다.

참고