[Algorithm] BFS (너비 우선 탐색)

1. BFS (Breadth-First Search)

 너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다.
 동작 과정에서 큐 자료구조를 이용한다.

---

• 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.

• 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에 방문하지 않은 노드를 모두 큐에 한 번에 삽입하고 방문 처리한다.

• 2번 과정을 더 이상 수행할 수 없을 때까지 반복한다.

---

그림으로 과정을 나타냈을 때, 다음과 같다.

이러한 과정을 반복하였을 때, 전체 노드의 탐색 순서(스택에 들어간 순서)는 다음과 같다.

 

python 코드로 구현하면 다음과 같다.