BFS 문서 원본 보기

{{공머생}}

Breadth First Search, 너비 우선 탐색이다. 말 그대로 가로 줄부터 몽땅 탐색하는거다. 

가로 줄부터 탐색하기 위해 큐(QUEUE) 라는 자료구조를 사용하게 된다.

[[DFS]]처럼 막힐때까지 가는게 아니라서 한갈래가 길이하 무한하고 탐색 대상이 다른곳에 있어도 탐색 할 수 있다. 그리고 적절히 응용하면 정점간의 최단거리도 구할 수있다.

의사코드는 다음과 같다.
  FUNCTION BFS(int src):
    ENQUEUE src
    while QUEUE is not empty:
      go = TOP_OF_QUEUE
      DEQUEUE
      Mark go as visited
      FOR i in graph[go]:
        if i is not visited:
          ENQUEUE i