Summary
- BFS (Breadth-First Search)
Description
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
- 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 삽입하고 방문 처리를 함
- 2의 과정을 더이상 반복할 수 없을 때까지 반복
bfs는 가까운 노드부터 탐색하므로, 모든 간선의 비용이 1인 그래프에서 bfs를 사용하면 최단 거리를 계산할 수 있음.
Data Structure
Time Complexity
정점의 수 : N, 간선의 수 : E
Code