너비 우선탐색 Breadth-First Search(BFS)

Breadth-First Search

---

Strategy: 얕은 노드를 먼저 확장한다.

Implementation: 프린지는 Queue(FIFO)로 구현한다.

Breadth-First Search Properties

---

- 탐색시간: 

- 프린지 용량은 얼마만큼 필요한가? 

- complete 한가? yes

- optimal 한가? 모든 코스트가 1일때는 optimal 하다. 예로 더 좋은 코스트가 더 깊은 곳에 있다면 optimal 하지 않다.