그래프 탐색
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한번씩 방문하는것
너비 우선 탐색(Breadth-first-search)
루트 노드(혹은 다른 임의의 노드)에서 시작해 인접한 노드를 먼저 탐색하는 방법
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법
- 깊게 탐색하기전에 넓게 탐색하는것
- 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 선택하는 방법
특징
- 재귀적으로 동작하지않는다.
- 어떤 노드를 방문했었는지 여부를 반드시 검사
- 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료구조인 큐(queue)를 사용
- 선입선출 원칙으로 탐색
- prim, Dijkstra 알고리즘과 유사하다.
과정
- 시작 노드를 방문한다.
- 큐에 방문된 노드를 삽입(enqueue)한다.
- 초기 상태의 큐에는 시작 노드만이 저장
- 큐에서 꺼낸 노드와 인접한 노드들을 모두 차례로 방문한다.
- 큐에서 꺼낸 노드를 방문한다.
- 큐에서 꺼낸 노드와 인접한 노드들을 모두 방문한다.
- 큐에 방문된 노드를 삽입한다.
- 큐가 소진될 때까지 계속한다.
