넓이우선탐색 (Breadth First Search)

BFS는 DFS와 다르게 Queue를 이용하여 그래프를 순회하는 방법이다. 

제일 먼저시작하는 노드를 큐에 push하고 색칠한 후에 시작한다. 그 다음에

① pop 하는 노드에서 인접한 노드들을 큐에 넣고 색칠한다.

② 더이상 넣을 노드들이 없다면 큐에서 pop을 한다.

이런식으로 동작한다. 예를 들어 설명해보자. 위에 그림에서 1에서부터 시작하므로

1을 큐에 넣고 방문했다고 색칠한다.

1을 pop하고 나면, 이제 1에 인접한 노드들을 확인 한다. 즉 2와 4를 push 하고 방문했다고 색칠한다.

현재 큐 상태는 1이 pop되어 있는 상태이고, 큐에 2와 4가 들어가있다.

이제 1에 인접한 모든 노드 2와 4를 큐에 넣었으므로 더이상 넣을 노드가 없다.

그러므로 현재 큐에서 pop을 해보면 front에 있는 2가 pop된다.

2가 pop되면 현재 그래프에 2에서 인접한 노드를 확인한다는 뜻이다.

2에 인접한 노드는 1, 3, 4가 있는데, 1과 4는 방문되었다고 표시했기 때문에

나머지 3을 큐에 push한다.

이제 2에 인접한 노드들은 다 방문했다고 표시되어 있기 때문에

큐에서 또 pop을 한다.

pop된 노드가 4이기 때문에, 이제 4에서 인접한 노드들을 확인하여야 하는데,

1과 2가 모두 방문됐다고 색칠되어 있기 때문에, 더이상 방문할 노드가 없다.

그래서 또 큐에서 pop한다.

3이 pop 되어 3에서 방문할 노드가 있는지 확인하여야 한다.

3의 인접노드는 3, 5, 6이므로

5, 6, 7을 큐에 push한다.

이제 3은 더이상 방문할 노드가 없기 때문에, 큐에서 5를 pop한다.

그런데 5에서 역시 3은 이미 방문해서 더 이상 방문할 노드가 없고,

한번더 6을 pop해도 6역시 3과 7 모두 방문 했다고 표시했기 때문에

더이상 방문할 노드가 없다. 그래서 또 pop을 한다.

7을 pop해도 역시 마찬가지로 인접노드를 모두 방문했기 때문에,

큐에서 pop하여야 하는데 큐가 비어있기 때문에 DFS가 종료된다.

결론적으로 위의 그래프를 DFS로 순회하면 1 -> 2-> 4 -> 3 -> 5 -> 6 -> 7 이다.

하지만 BFS하면 1 -> 2 -> 3 -> 5 -> 6 -> 7 -> 4 이므로 DFS와 BFS가 그래프를 순회하면

다른 순서로 순회하는 것을 볼 수 있다.

---

BFS를 더 정확히 이해 하기 위해서 또 다른 예제로 한번 해보자. 처음에 BFS를 공부할 때에는 헷갈리기 때문에

큐를 직접 그려가보면서 해야 이해가 쉽다. 위와 하는 방법이 똑같기 때문에 스스로 한번 해보고

밑에 순서대로 큐가 변하는 모습을 보면 이해할 수 있다.