[알고리즘] 너비 우선 탐색(Breadth First Search, BFS)

오늘은 너비 우선 탐색을 공부를 해보자. DFS를 공부했는데 다른 방식으로 탐색하는 알고리즘이 있어서 정리하게 되었다.

1. 개념

너비 우선 탐색은 DFS와는 조금 다르게 너비를 우선적으로 탐색하는 알고리즘이다. 큐(Queue)를 사용하여 노드를 탐색한다.

2. BFS 작동 순서

1. 큐에서 노드를 하나 뺀다.
2. 해당 노드에 연결된 노드 중 방문하지 않는 노드를 방문하고 차례대로 큐에 삽입
3. 위의 방법을 반복한다.(다 끝날때까지)
4. 탐색 순서 결과를 확인한다.

4. 예시

건물에서 한 실외기에서 시작하여 센서노드까지 탐색하려면 DFS를 적용하면 좋지만, 실외기 단위에서 다수의 실외기 정보를 종합하고 탐색하는 경우에는 DFS보다는 BFS 방식으로 탐색하는 것이 더욱 효율적일 것이다. 왼편에는 1개의 그래프가 있고 오른편에는 큐가 있다고 생각해보자.

큐에 시작 노드(1번 노드)를 삽입하고, 방문 처리 한다.(DFS랑 뭔가 비슷한 느낌이 든다.)

1번 노드를 큐에서 빼서 1번 노드에 연결된 노드 중 방문하지 않은 노드(2, 3번 노드)를 방문하고 차례대로 큐에 삽입하고 방문처리 한다.

2번 노드를 큐에서 빼서 2번 노드에 연결된 노드 중 방문하지 않은 노드(4, 5번 노드)를 방문하여 큐에 삽입하고 방문처리 한다.(2번 노드의 인접 노드 중 방문한 노드(1, 3번 노드)는 패스)

3번 노드를 큐에서 빼서 3번 노드에 연결된 노드 중 방문하지 않은 노드(6, 7번 노드)를 방문하여 큐에 삽입하고 방문처리 한다.(3번 노드의 인접 노드 중 방문한 노드(1, 2번 노드)는 패스)

모든 노드를 다 방문했으므로, 큐에서 4번 노드에서 7번 노드까지 순서대로 빼내서 순서를 탐색 순서를 결정해준다.

결정된 탐색순서는 아래와 같다.(시작 노드와 가까운 곳부터 차근차근 탐색한다.)