Breadth-first  Search

컴퓨터과학 에서 breadth-first search (BFS) 는 트리 (Tree), 그래프 (Graph) 를 탐색하는 tree search algorithm 이다. 보통 root node에서 출발하여 모든 이웃하는 노드들을 탐색한다. 또한 가장 가까운 노드들 각각에 대해 탐색하지 않은 이웃 노드들을 탐색하여 목표를 찾을 때까지 계속한다.

BFS 는 해 (solution)를 찾아서 조직적으로 트리의 모든 노드들을 검사하는 무정보 탐색 (Uninformed or Blind Search) 이다. 달리 말하면 목표에 대한 고려없이 목표가 발견될 때 까지 전체 트리를 전부 탐색한다 (exhaustively searches). BFS 는 휴리스틱 (Heuristic)  을 사용하지 않는다.

알고리즘의 관점에서 보면, 노드를 확장하여 얻어진 모든 자식 노드들이 FIFO queue 에 더해진다. 실제로 구현시, 이웃 노드들을 위해 아직 검사되지 않은 노드들은  "open" 상태 라고 불리는 어떤 용기 (queue 또는 linked list 같은 것) 에 놓여지게 되고, 일단 검사되면 "closed" 라고 불리는 용기에 놓여진다.

트리가 아닌 unweighted cyclic graph 에서 최단경로를 찾기위해 탐색할 때는, BFS 는 이미 방문했었다는 것을 나타낼 필요가 있기 때문에 각 노드에 하나의 bit 를 가지게 하여 적응할 수 있다.

• BFS 는 완전하다 (complete) -  만일 존재한다면 목표 (goal)을 찾는다. (즉 트리상의 모든 노드에 도달한다)
• BFS 는 최적이다 (optimal) - 목표에 도달하는 가장 적은수의 단계 (steps) 를 찾는다.
• BFS 는 메모리상에 모든 확장된 노드들을 저장할 필요가 있기 때문에 탐색하는 트리 또는 그래프의 크기 (edges 더하기 vertices) 에 비례하는 공간복잡도 (space complexity)를 가진다.
• BFS 는 탐색하는 트리 또는 그래프의 크기 (edges 더하기 vertices) 에 비례하는 시간복잡도 (time complexity) 를 가진다.

위의 그래프에서 BFS 는 A에서 출발하며, 왼쪽의 edge를 오른쪽의 edge 보다 먼저 선택한다고 가정하면, 방문하는 노드의 탐색 순서는 다음과 같다. 깊이우선 탐색 (Depth First Search) 와 비교해 보자 (Wikipedia : Breadth-first Search).

A, B, C, E, D, F, G.

Pseudocode :

BFS(Start,Goal)

push(Queue,Start)
while(notEmpty(Queue))
  Node <- Pop(Queue)
  if (Node == Goal)
    return Node
  forall Child <- Expand(Node)
    push(Queue, Child)

Depth First Search    Iterative Deepening Depth-first Search   best-first search

Site :

Graph Algorithms : BFS java code

BFS-Applet

Breadth First Search : Demo

Dictionary of Algorithms and Data Structures: breadth-first search

C++ Boost Graph Library: Breadth-First Search

Paper :

나비우선 탐색 (Breadth-First Search) : Dan W. Patterson

너비우선 탐색 (Breadth-First Search) : Nils J.Nilsson