"꼼꼼하게 좌우를 살피며 다니자"와 같이 시작 정점으로부터 가까운 정점을 먼저 방문하고
멀리 떨어져 있는 정점을 나중에 방문하는 알고리즘이다.
시작 정점을 지나고 나면 깊이가 1인 모든 정점을 방문하고, 그다음에는 깊이가 2인 모든 정점을 방문한다.
이런 식으로 한 단계씩 깊이를 더해가며 해당 깊이에 있는 모든 정점들을 방문해 나가다가 나중에는 더 이상 방문할 곳이 없을 때 탐색을 종료한다.
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
큐(Queue)를 이용
정점의 수가 n이고, 간선의 수가 e인 그래프의 경우
그래프가 인접 리스트로 표현된 경우 O(n+e)
인접 행렬로 표현된 경우 O(n^2)이다.
희소 그래프인 경우 인접 리스트의 사용이 인접 행렬보다 유리
(희소 그래프는 그래프 내에 적은 수의 간선을 가지는 그래프로 인접 행렬을 사용하면 메모리의 낭비가 크기 때문)