BFS(Breadth First Search, 너비우선탐색)

자료출처 : https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVIoJqqfYDFAWg

SW Expert Academy

 

BFS는 그래프 탐색 알고리즘 입니다.

BFS는 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작으로 하여 다시 인접한 장점들을 차례로 방문하는 방식이다.

인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 Queue를 활용한다.

 

위의 내용은 어려움으로 개인적으로 추가 큐가 빌때까지 혹은 목적을 달성할때 까지 반복하는데 현재 노드에서 이동할 수 있는 노드들을 큐에 넣어준다. 넣어준 순서대로 이동을 하게되므로 연결되어있는 부분부터 보게된다. 최단거리를 찾는다면 BFS 이용시 찾는순간이 바로 최단거리가 된다. DFS를 이용하게 된다면 모든 경로를 찾아야 최단거리라고 볼수가 있다.

 

BFS를 이용한 문제풀이

https://mungto.tistory.com/166

미로의 거리 Python(SW Expert Academy)

https://mungto.tistory.com/165

노드의 거리 Python(SW Expert Academy)

 

이미지 출처 : 위키백과

https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89