BFS

그래프 탐색 : 어떤 것들이 연속해서 이어질때, 모두 확인하는 방법

 

그래프 :  Vertex(어떤 것) + Edge(이어지는 것)

 

그래프 탐색 종류

- BFS : Breadth-first search(너비 우선 탐색)

- DFS : Depth-first search(깊이 우선 탐색)   

 

BFS : 1 2 5 3 4 6 

DFS : 1 2 3 4 6 5

 

---

 

BFS 

 

아이디어

 

- 시작점에 연결된 Vertex를 찾기

- 찾은 Vertex를 Queue에 저장

- Queue의 가장 먼저 것 뽑아서 반복

 

 

시간 복잡도

 

-BFS : O(V+E)

 

자료구조

 

- 검색할 그래프

- 방문여부 확인(재방문 금지)

- Queue : BFS  실행