Skip to content

너비 우선 탐색 (BFS)

수정하기
문서 생성 2022-05-02 16:28:24 최근 수정 2022-05-02 18:24:23
  • 그래프 순회
  • DFS가 한 쪽으로만 계속 진행하다가 끝을 본 뒤 다른 곳으로 옮긴다면, BFS는 모든 곳을 조금씩 진행한다.
  • 각 단계 정점들이 안에서 방문 순서가 바뀔 순 있지만 다른 단계와 섞이지 않는다.
    • 루트 노드에 방문한 것을 0단계, 그 다음부터 1, 2, 3단계라 하면 k단계에 방문하는 정점은 시작점으로부터 최단거리가 k인 것