알고리즘 7장
그래프 탐색: BFS 기본 템플릿
BFS는 큐에 들어간 순서가 레벨 순서를 만들기 때문에, enqueue 시점 방문 처리가 BFS의 핵심 불변식입니다.
BFS 큐 상태 변화
큐 트레이스
1
2
3
4
5
queue trace
1
2
3
visited
1
2
3
enqueue 전에 방문 표시를 끝내 중복 삽입을 막습니다.
BFS 방문 불변식
점검
큐 queue
먼저 들어간 정점부터 꺼내 같은 레벨을 순서대로 처리합니다.
방문 visited
enqueue 전에 표시해 같은 정점이 여러 번 들어가지 않게 합니다.
frontier
현재 레벨에서 다음 레벨로 확장되는 경계입니다.
복잡도
정점과 간선을 한 번씩 보므로 O(V+E)입니다.