BFS

너비 우선 탐색 BFS (Breadth-Frist Search)

 

완전 탐색 방법 중 하나

시작 노드에서 출발해서 시작 노드 기준 가장 가까운 노드를 방문하면서 탐색하는 알고리즘

- 큐 구조 이용

탐색 방식: 선입선출 (queue 이므로!)

 

1. BFS 시작할 노드 정한 후 사용할 자료구조 초기화하기

방문했던 노드를 다시 방문하지 않음 -> 체크리스트 필요

그래프를 인접 리스트로 표시 (탐색에 스택이 아닌 큐 이용)

 

2. 큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입

큐에서 노드를 꺼내며 인접 노드 큐에 삽입

방문 리스트 체크 (방문 이미 완료 시 삽입하지 않음)

 

3. 큐 자료 구조에 값이 없을 때까지 반복하기

 

그림으로 표현하면 아래와 같다!