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