너비 우선 탐색 (Breadth First Search, BFS)

너비 우선 탐색

- 연결 graph, 무방향 graph

- queue 사용

 

 

단계

① 시작 정점 v 방문

② v에 인접한 모든 정점들 방문

③ 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들 방문

④ 더 이상 방문할 정점 없으면 종료

 

 

ex) 0 – 1 – 2 – 3 – 4- 5 – 6 – 7 순으로 방문

 

 

분석

① 인접 리스트 사용

    리스트 node 수 2e개 만큼 조사 → O(e) 소요

② 인접 행렬 사용

    한 정점에 인접한 정점들 조사하는데에 O(n) 소요

    ∴ 전체 원소 조사 → O($n^2$) 소요