(Data_Structure) BFS (Breadth-First Search)

BFS(Breadth-First Search)은 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다.

시작 노드로부터 거리에 따라 레벨 단위로 탐색하고 같은 레벨의 노드들을 모두 방문하면 다음 레벨의 노드들을 방문한다.

 

BFS는 Queue를 사용하여 구현한다.

BFS Algorithm Pseudocode 를 보면

Algorithm BFS(G,s)
 L_0 <- new empty sequence
 L_0.insertBack(s)
 s.setLabel(VISITED)
 i<-0
 while ￢L_i.empty()
   L_i+1 <- new empty sequence
   for all v in L_i.elements()
     for all e in v.incidentEdges()
       if e.getLabel() = UNEXPLORED
         w <- e.opposite(v)
         if w.getLabel() = UNEXPLORED
           e.setLabel(DISCOVERY)
           w.setLabel(VISITED)
           L_i+1.insertBack(w)
         else
           e.setLabel(CROSS)
   i <- i+1

 

아래는 그림 진행 순서 예시이다.

BFS는 그래프의 구조를 레벨 단위로 탐색하기에

 

문제) 최단 경로, 최단 weight값을 찾는 문제에 유용하게 사용된다.