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

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

 

위키 bfs

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를 빼서 갈 수 있는 곳을 넣어야 하는데 없으니깐 넘어감

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

 

 

참고

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89