Summary

• BFS (Breadth-First Search)

Description

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 함
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중 방문하지 않은 노드들을 큐에 삽입하고 방문 처리를 함
3. 2의 과정을 더이상 반복할 수 없을 때까지 반복

bfs는 가까운 노드부터 탐색하므로, 모든 간선의 비용이 1인 그래프에서 bfs를 사용하면 최단 거리를 계산할 수 있음.

Data Structure

• Queue

Time Complexity

정점의 수 : N, 간선의 수 : E

• 인접 리스트로 표현된 그래프 : O(N + E)
• 인접 행렬로 표현된 그래프 : O(N^2)

Code