queue를 이용하여 간단히 구현 가능.

진행 정도에 따라 coloring을 함.
흰색(방문x)->회색(방문예정,q에 있는 상태)->검은색(방문끝)
회색은 발견된 정점과 발견하지 않은 정점의 경계선을 나타낸다

수행시간은 인접리스트 O(V+E), 인접행렬 O(V^2)

이론

u.d : (s,u) 까지 최단 경로가 저장된다.
(s,v) <= (s,u)+1
s에서 u로 도달가능하면 s에서 v도 도달 가능하다.
BFS가 끝났을 때 각 정점에 계산된 v.d는 v.d >= (s,v)를 만족한다.
BFS에서 Queue안에 정점들은 최대 Layer 2개로 구성되어 있다. 
즉, Queue안에 정점들은 최대 Layer가 1개 차이

소스 코드

for 각 정점 u {
    u.color = WHITE
    u.d = INF       // s부터 u까지 거리
    u.p = NULL      // u 정점의 직전원소(부모)
}
s.color = GRAY
s.d = 0
s.p = NULL
enqueue(s)
while(!q.empty()){
    u = dequeue();
    for u와 연결된 정점 v {
        if (v.color == WHITE){
            v.color = GRAY
            v.d = u.d + 1   // edge 가중치 1, 진행하는 layer라고도 볼 수 있음
            v.p = u
            enqueue(v)
        }
    }
    u.color = BLACK
}