알고리즘 -BFS(Breadth First Search)

그래프를 탐색하는 방법중 하나.

최단거리, 최소비용등 최솟값을 구하는 문제에 적용할 수 있는 방법.

 

그래프 정점 사이의 거리가 1일때만 가능.

 

0. 시작할 정점을 저장함. 

1. 저장된 정점에서 첫번째 정점를 선택. 저장에서 제거

2. 제거한 정점에서 할 작업 선택. 

3. 제거한 정점과 연결된 정점중 방문하지 않은 모든 정점 저장.

4. 저장한 정점이 모든 노드가 삭제 될때까지 2~3 반복.

 

저장할 자료구조는 큐로 하는것이 편함..

 

앞에서부터 탐색해나가야되기 때문.

FIFO 구조면 저장된 정점을 앞에서 부터 하나씩 볼수 있기 때문.