너비 우선 탐색 (Breadth First Search, BFS)
·
PS/Algorithm
BFS는 그래프나 트리의 자료구조에 적용할 수 있는 맹목적 탐색 알고리즘이다. 맹목적 탐색은 주어진 정보에 따라 효율적인 탐색을 실시하는 것이 아닌 이미 정해진 순서로 탐색을 실시하는 방법으로 실용적으로 따져볼 때 매우 비효율적인 알고리즘이지만 구현이 쉽고 간단한 문제에 한해 아주 유용하다. 이름 그대로 트리에서 노드를 깊게 파고드는 것보다 한 계층을 순차적으로 모두 살펴보는 것을 우선하는 알고리즘이다. BFS는 Queue로 구현할 수 있다. 1. 탐색을 시작할 정점을 Queue에 삽입한다. 2. Queue가 비었다면 '9'로 이동한다. 3. Queue의 가장 위에 있는 정점이 현재 탐색 중인 정점이다. 4. 탐색 중인 정점이 찾으려는 자료이면 '8'로 이동한다. 5. 탐색 중인 정점과 연결된 정점을 Q..
전라남도교육지원청
'알고리즘' 태그의 글 목록