[Algorithm] Breadth-first search (너비 우선 탐색)

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

출처 : 위키백과

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

예)

① 1을 방문하며 큐에 넣는다.

② 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드들을 차례로 방문하며 큐에 넣는다.

(1을 빼며, 1과 인접한 2, 3을 차례로 큐에 넣는다.)

③ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드들을 차례로 방문하며 큐에 넣는다.

(2를 빼며, 2와 인접한 4, 5, 6을 차례로 큐에 넣는다.)

④ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(3을 빼며, 3과 인접한 7을 큐에 넣는다.)

⑤ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(4를 빼며 4와 인접한 숫자를 넣어야 하지만, 4와 인접한 숫자가 없으므로 패스한다.)

⑥ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(5를 빼며, 5와 인접한 8을 큐에 넣는다.)

⑦ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(6을 빼며 6과 인접한 숫자를 넣어야 하지만, 6과 인접한 숫자가 없으므로 패스한다.)

⑧ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(7을 빼며 7과 인접한 숫자를 넣어야 하지만, 7과 인접한 숫자가 없으므로 패스한다.)

⑨ 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드를 방문하며 큐에 넣는다.

(8을 빼며 8과 인접한 숫자를 넣어야 하지만, 8과 인접한 숫자가 없으므로 패스한다.)

⑩ 큐에 뺄 숫자가 없으므로 종료한다.