너비 우선 탐색(Breadth First Search)는 BFS라고도 하며 그래프를 순회하는 방법중 하나이다. 너비 우선 탐색은 깊이 우선 탐색과 다르게 인접한 정점을 모두 방문한 후 정점을 방문한 순서대로 다시 모든 인접한 정점을 방문하는 방식의 탐색 방법이다. 너비 우선 탐색은 큐로 구현을 할 수 있다. 너비 우선 탐색 방법은 다음과 같다.
- 너비 우선 탐색이 시작될 정점 v를 선택한다.
- 선택된 정점 v에 대해 방문 표시와 방문 처리를 하고 큐에 삽입한다.
- 큐의 front에서 꺼낸 정점의 인접 정점들에 대해 방문되지 않은 정점들을 큐에 삽입하고 방문 처리를 한다.
- 큐가 공백이 될 때까지 3의 과정을 반복한다.
다음은 너비 우선 탐색의 예시이다.
정점 0 방문
정점 0을 방문한 후 큐에 0을 넣는다.
정점 3 방문
정점 0을 Dequeue하고 정점 3을 방문한 후 큐에 0을 넣는다.
정점 2 방문
정점 2를 방문한 후 큐에 2를 넣는다.
정점 1 방문
정점 1을 방문한 후 큐에 1을 넣는다.
정점 5 방문
정점 3의 인접 정점을 방문하기 위해 3을 Dequeue하고 정점 5를 방문한 후 큐에 5를 넣는다.
정점 4 방문
정점 4를 방문한 후 큐에 4를 넣는다.
정점 6 방문
2와 1의 인접 정점을 방문하기 위해 Dequeue를 하지만 인접한 정점은 모두 방문했기 때문에 스택에서만 빠지게 된다. 다음 정점 5의 인접 정점을 방문하기 위해 Dequeue하고 정점 5의 인접 정점은 6을 방문한 후 큐에 넣어준다.
너비 우선 탐색 종료
모든 정점을 방문했기 때문에 큐에 남아있는 4와 6은 정의된 함수(BFS 함수)의 기능에 따라 별도의 인접 정점 방문없이 모두 큐에서 빠진다.
'자료구조' 카테고리의 다른 글
| 신장 트리(Spanning Tree) (0) | 2022.03.30 |
|---|---|
| 깊이 우선 탐색(DFS : Depth First Search) (0) | 2022.03.30 |
| 그래프 표현 (2) | 2022.03.30 |
| 그래프(Graph) (0) | 2022.03.30 |
| AVL 트리(AVL Tree) (0) | 2022.03.29 |