BFS(Breadth Firsh Search)
그래프를 탐색하는 방법은 2가지가 있음
- 깊이 우선 탐색(DFS)
- 너비 우선 탐색(BFS)
BFS
- 탐색 시작점의 인접한 정점부터 먼저 다 방문한 후,
그 방문한 정점을 시작으로 다시 인접한 정점들을 차례로 방문하는 방식
- 인접한 정점에 대해 탐색 후 다시 BFS를 진행하므로, FIFO인 큐를 활용함
BFS 예제
1. 초기 상태
visited 배열 초기화
Q 생성
시작점을 enqueue
2. A점부터 시작(root=1)
dequeue : A
A visited
A의 인접점들을 enqueue
3. 탐색 진행(A의 인접점인 B,C,D를 순차적으로)(root=2)
dequeue : B , B visited , B의 인접점들을 enqueue
dequeue : C , C visited , C의 인접점들을 enqueue
dequeue : D , D visited , D의 인접점들을 enqueue
4. 탐색 진행(B,C,D의 인접점인 E,F,G,H,I를 순차적으로)(root=3)
dequeue : E , E visited , E의 인접점들을 enqueue
dequeue : F , F visited , F의 인접점들을 enqueue
dequeue : G , G visited , G의 인접점들을 enqueue
dequeue : H , H visited , H의 인접점들을 enqueue
dequeue : I , I visited , I의 인접점들을 enqueue
5. Q가 비었으면 탐색 종료
