BFS

Breadth First Search, 너비 우선 탐색이다. 말 그대로 가로 줄부터 몽땅 탐색하는거다. 가로 줄부터 탐색하기 위해 큐(QUEUE) 라는 자료구조를 사용하게 된다.

의사코드는 다음과 같다.

 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