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

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

• 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법
• 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
• OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다.

 

• 재귀적으로 동작하지 않는다.
• 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. (즉, 선입선출(FIFO) 원칙으로 탐색)

 

시간복잡도

• 인접 리스트로 표현된 그래프 : O(N+E)
• 인접 행렬로 표현된 그래프 : O(N^2)

---

구현 방법

• 자료 구조 큐(Queue)를 이용

 

활용

• 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

---

장점

• 출발노드에서 목표노드까지의 최단 길이 경로를 보장한다.
• 노드의 수가 적고, 깊이가 얕은 경우 빠르게 동작할 수 있다.
• 단순 검색 속도가 깊이 우선 탐색(DFS)보다 빠르다.

 

단점

• 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 보다 많은 기억 공간을 필요로 하게 된다.
• 해가 존재하지 않는다면 유한 그래프(finite graph)의 경우에는 모든 그래프를 탐색한 후에 실패로 끝난다.
• 무한 그래프(infinite graph)의 경우에는 결코 해를 찾지도 못하고, 끝내지도 못한다.

---

References

 

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

너비 우선 탐색 - 위키백과, 우리 모두의 백과사전

gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog

coding-factory.tistory.com/612

[Algorithm] BFS 알고리즘 (Breadth-First Search)