BFS(Breadth-First Search)

 

BFS(Breadth-First Search)

 

너비 우선 탐색.

 

이름 그대로 그래프에서 넓은 부분을 우선적으로 탐색하는 알고리즘을 말한다.

 

직접 그려본 BFS

 

BFS의 탐색 순서

 

BFS는 A에서 출발해서 A에서 인접한 노드인 B, C부터 우선적으로 모두 탐색한다.

그 다음 B, C에서 인접한 노드인 D, E, F, G.

그 다음 F, G는 마지막 노드이니, D, E에서 인접한 노드인 H, I, J를 하나씩 탐색하면

모든 노드의 탐색이 끝나게 된다. 

 

이때, 각 단계의 노드들은 그 안에서 방문 순서가 바뀔 수는 있지만,

다른 단계의 노드와는 방문 순서가 바뀔 수 없다.

 

여기서 가장 처음 시작하는 0단계 노드에서 K단계 노드까지는

최단거리가 K가 된다.

 

최단거리는 즉, A에서 마지막 노드까지 가는 데 필요한 간선의 최소 개수와 같다.

 

BFS의 구현

 

BFS를 구현하기 위해서는 큐를 이용한다.

 

1. 우선 시작 노드를 큐에 넣는다.

2. 큐에서 노드를 하나 꺼낸다.

3. 해당 노드를 방문한다.

4. 해당 노드와 인접한 모든 미방문 노드를 큐에 넣는다.

5. 큐가 모두 비워질 때까지 2, 3, 4번 반복.