목차
1. 너비 우선 탐색이란? (BFS : Breath First Search)
- 그래프의 인접한 정점을 우선적으로 탐색
- queue를 이용하여 구현한다.
- 장점 : 탐색된 경로가 항상 최단 경로이다, queue를 사용하여 다음 탐색 정점을 지정하므로 DFS 보다 메모리를 적게 사용한다.
- 단점 : 목표 노드의 깊이가 깊은 경우 탐색이 오래 걸린다.
2. BFS 구현
(※ 입력 기준 : BFS 애니메이션)
※ 참조
위키 백과 너비 우선 탐색 :
https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89
'C++ > 자료구조' 카테고리의 다른 글
| [C++] 정렬 #3 병합 정렬 & 퀵 정렬 (Merge Sort & Quick Sort) (0) | 2023.07.03 |
|---|---|
| [C++] 정렬 #2 삽입 정렬 & 힙 정렬 (Insertion Sort & Heap Sort) (0) | 2023.06.30 |
| [C++] 정렬 #1 버블 정렬 & 선택 정렬 (Bubble Sort & Selection Sort) (0) | 2023.06.29 |
| [C++] 트리 #2 DFS (0) | 2023.06.26 |
| [C++] 트리 #1 Tree (0) | 2023.06.24 |