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
}
Leave A Comment