[알고리즘] 너비 우선 탐색(BFS, Breadth,First Search) - 컴도리돌이

너비 우선 탐색

---

• 너비 우선 탐색(BFS, Breadth, First Search)은 시작 정점을 경계에 추가하는 것으로 시작한다. 경계는 이전에 방문했던 정점들에 의해 구성된다. 그리고 현재 경계에 인접한 정점을 반복적으로 탐색한다. 다음에 나오는 그림을 보면서 BFS 동작에 대해 짐작하면 좋다.
• 시간 복잡도 : O(V+E)
• BFS는 시작 정점에서 가까운 정점을 찾는데 적합하다.
• BFS에서 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장한다.
• 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#/media/%ED%8C%8C%EC%9D%BC:Animated_BFS.gif

 

너비 우선 탐색 관련 문제

---

[프로그래머스]

 

2021.08.10 - [컴도리돌이 전공 공부/C++] - [프로그래머스/C++] 네트워크 - 컴도리돌이