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

1. 너비 우선 탐색 너비 우선 탐색은 시작 정점으로부터 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문하는 방법이다. 깊이 우선 탐색과 반대의 움직임을 보인다고 생각하면 된다. 깊이 우선 탐색이 세로 본능이라면 너비 우선 탐색은 가로본능이라고 생각하면 된다. 정확히는 거리로 보면 된다. A에서 1떨어진 노드는 B, C 다. 고로 B와 C는 형제다. 하지만 B, C와 A는 부모-자식 관계다. 깊이 우선 탐색은 자식부터 탐색을 하는 구조다. 하지만 너비 우선 탐색은 주변 인접노드, 형제를 먼저 탐색하는 구조다. 너비 우선 탐색은 인접한 정점들에 대해서 차례로 다시 너비 우선 탐색을 반복해야 하므로 선입 선출의 구조를 갖는 큐 자료구조를 사용한다. 2..

2020.06.23