C++/자료구조
[C++] 트리 #3 BFS
노랑꼬리
2023. 6. 28. 11:22
목차
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