이번에 살펴볼 개념은 BFS(너비 우선 탐색)에 관한 내용입니다.
BFS(Breadth First Search, 너비 우선 탐색)
DFS는 스택 자료구조를 활용해 구현했었다면, BFS는 Queue를 활용합니다.
DFS는 갈 수 있는 곳까지 들어가서 확인하고, 갈 곳이 없으면 다시 되돌아와 다른 길을 찾는 식이었습니다. 이를 깊이 우선 탐색이라고 부릅니다.
BFS는 시작점의 인접한 정점들을 차례로 모두 방문하고, 방문했던 정점을 시작점으로 해서 다시 인접한 정점들을 차례로 모두 방문하고 하는 방식으로, 너비 우선 탐색이라고 부릅니다.
위 그림에서 BFS(너비 우선 탐색)을 진행한다면, 시작점을 A라고 하였을 때 A-B-C-D-E-F 순으로 탐색하게 됩니다.
BFS의 탐색 과정
BFS는 방문 노드의 인접한 노드를 큐에 저장하는 것이 DFS와 다른 점입니다.
방문했다는 정보를 남기는 visited 배열은 동일하게 사용합니다.
[1] 처음 시작 노드 방문 (A)
[2] A는 큐에서 삭제 및 방문 표시 후 A의 인접 노드들을 큐에 삽입
[3] A의 인접노드들 중 가장 큐에 먼저 들어간 B를 큐에서 삭제 및 방문 표시, B의 인접 노드들을 큐에 삽입
[4] C를 큐에서 삭제 및 방문 표시, C의 인접 노드를 큐에 넣으려 했으나 없으므로 skip
[5] 마찬가지로 D도 큐에서 삭제 및 방문 표시, D의 인접 노드 G를 큐에 삽입
[6] 큐에 남아있는 요소들을 차례대로 위와 같은 방법으로 방문 및 표시하면서 결과적으로 BFS 탐색 완료(큐가 완전히 비게 될 때)
※ BFS를 직접 코드상에서 구현할 때에는 deQueue 연산으로 큐의 맨 앞에 있는 것이 무엇인지 알아내는 것이므로, 큐에서 먼저 빼낸 후(deQueue) 그와 동시에 그 노드의 방문 표시를 할 수 있게끔 합니다.