한 단계씩 넓혀 가기
시작점과 바로 연결된 정점들을 먼저 발견하고, 그다음 두 간선을 거쳐 도달하는 정점들을 찾는다. 이웃을 적은 순서에 따라 같은 단계 내부의 방문 순서는 달라질 수 있지만, 시작점으로부터의 단계 순서는 유지된다.
큐와 방문 표시
발견한 정점을 큐에 넣고 앞에서 하나씩 꺼내 이웃을 살핀다. 같은 정점이 여러 경로에서 발견될 수 있으므로 방문 상태를 관리해야 한다. 큐에 넣을 때 발견 표시를 하면 같은 정점을 불필요하게 여러 번 넣는 일을 줄일 수 있다.
최단 경로의 조건
간선마다 이동 비용이 같다면 먼저 도달한 단계가 최소 이동 횟수다. 서로 다른 비용을 가진 간선에서는 단순 BFS가 최소 비용 경로를 보장하지 않는다. 짧은 간선 수와 작은 비용 합은 같은 기준이 아니다.
도달하지 못하는 정점
한 시작점에서 탐색하면 그 점으로부터 도달 가능한 부분만 방문한다. 그래프 전체를 처리하려면 미방문 정점에서 탐색을 다시 시작하는 등의 절차가 필요하다. 방향 그래프에서는 간선의 방향에 따라 도달 가능성이 달라진다.
관련 문서
깊이 우선 탐색 / 큐 / 그래프 (자료 구조) / 알고리즘 / 자료 구조