너비 우선 탐색

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 를 사용해야만 레벨 순서대로 접근이 가능하다.

너비 우선 탐색 기법의 장점과 단점[편집]

장점
  • 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
단점
    • 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
    • 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
    • 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

같이 보기[편집]