korean IT student

너비 우선 탐색(Breath First Search, BFS) - 시작점에서 가까운 정점부터 순서대로 방문을 하는 탐색 알고리즘이다. 큐와 같이 사용된다. - 최단 경로를 구할 때 목적지를 찾자마자 최단경로임이 보장되어 탐색을 종료할 수 있는 장점이 있다. - 가까운 정점을 모두 저장해놓고 순서대로 방문해야 하므로 스택 구조는 구현이 어렵고 큐를 사용. 그림을 보며 이해를 해보자. 1에서 시작을 한다. 1은 큐에 저장 된다. 1에서 인접한 노드를 방문한다. 방문한 1은 큐에서 꺼내고 방문한적 없는 노드인 2, 3을 큐에 넣어준다. 방문한 2, 3 은 큐에서 꺼내고 방문한적없는 4, 5를 큐에 넣어준다. 모든 노드가 방문처리 되면 남은 노드들을 큐에서 꺼내준다. 큐에서 꺼낸 순서는 1, 2, 3, 4, 5..