BFS

BFS는 Breadth First Search의 약자로 컴포넌트의 모든 정점을 한번씩 순회한다. DFS와 대립되는 성질을 갖고있다. 물론 컴포넌트 개수를 세거나 각 컴포넌트의 크기를 구하는 데는 DFS와 BFS 모두 사용할 수 있다.

깊이를 중시하는 DFS와 달리 BFS는 넓이를 중시한다.

각 단계의 정점들은 그 안에서 방문 순서가 바뀔수는 있지만 다른 단계와는 방문 순서가 절대 뒤섞이지 않는다.

여기서 0번 노드 즉, 시작점을 방문한 것을 0단계라고 하고, 그 다음부터 1, 2, 3단계라고 부를 때, k단계에 방문하는 정점들은 시작점으로부터 최단거리가 k이다.
최단거리는 위의 그래프에는 가중치가 없으니 A에서 B로 이동하는 최소 개수의 간선이라고 볼 수 있다.

BFS는 탐색은 하되, 각 정점의 최단거리를 재야 할 때 요긴하게 쓰인다.