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

너비 우선 탐색(BFS)이란?

시작점으로 부터 인접한 지점을 먼저 탐색하는 방법

• 노드란 장소, 지점, 위치로 생각해주시면 됩니다.
• 시작 노드로 부터 가까운 곳을 먼저 방문하고 멀리 있는 곳을 나중에 방문하는 방법입니다.
• 사용 예시로는 두 장소 사이의 최단 경로, 또는 A가 B 장소에 방문하는지의 여부가 있습니다.

특징

• 어떤 노드를 방문했었는지의 여부를 반드시 확인해야 합니다.
• 큐(Queue)를 사용합니다.

너비 우선 탐색(BFS)의 과정

1. 탐색 시작 노드를 큐에 삽입 후 방문 했다는 표시를 합니다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 합니다.
3. 2번의 과정을 큐의 크기가 0이 될때까지 반복합니다.

예시)

• 시작 지점은 A 입니다.

1) A를 시작점으로 하여 A 노드는 큐에 저장하고 방문 처리를 합니다.

2) A와 인접한 B, D를 차례로 방문하고 B, D를 큐에 저장하고 방문 처리를 합니다. 이 때 A는 큐에서 삭제 합니다.

3) B와 인접한 C를 방문하고 C를 큐에 저장 후 방문처리를 합니다. 이 때 B는 큐에서 삭제 합니다.

4) D와 인접한 노드가 없어 방문할 곳이 없습니다. D를 큐에서 삭제 합니다.

5) C와 인접한 E를 방문하고 E를 저장 후 방문처리를 합니다. 이 때 C는 큐에서 삭제 합니다.

6) E와 인접한 노드가 없어 방문할 곳이 없습니다. E를 큐에서 삭제 합니다. 이 때 더 이상 큐에 저장된 값이 없으므로 종료합니다.