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

이번 포스팅은 그래프를 탐색하는 알고리즘 중 하나인 너비 우선 탐색(BFS)에 대해 알아보려고한다. 

 

[자료구조] 그래프 (Graph)

 

현재 차근차근 해보자는 생각에 기초 공부를 하는 중이다. 좀 더 자세한 내용은 다른 글에 작성하거나 추후 글을 수정하는 방향으로 작성해 보겠다. 

틀린 내용이 있거나 궁금한게 있다면 편하게 댓글 남겨주시면 감사하겠습니다!

---

 

📝 개념

처음 시작할 때 그래프의 구조를 모르는 상태에서, 어떤 정점(시작점이라고 함)에 위치 하고 있다고 가정해보자. 

목적은 시작점에서 간선을 따라가며 정점을 탐색하여 지정한 정점(목표)에 도달하는 것이다.

지정된 정점에 도착하면 해당 정점이 목표인지 여부를 판단하는데, 너비 우선 탐색은 정점을 탐색할 때 시작점에서 가까운 정점 부터 탐색한다.

 

너비 우선 탐색

현재 위치는 빨간색 테두리로 표시해두었다.

A를 시작점, G를 목표라고 하겠다.

 

너비 우선 탐색

A에서 도달할 수 있는 정점 B, C, D가 다음으로 이동할 후보가 된다.

후보가 되는 정점은 연두색 테두리로 표시할 것이다.

 

너비 우선 탐색

후보 중에서 정점 하나를 선택한다. 선택의 기준은 가장 먼저 후보에 추가된 것이다. 동시에 추가된 후보 중에는 어떤 것을 선택해도 무방하다. 여기선 왼쪽에 있는 정점부터 선택하겠다.

B, C, D가 같은 시점에 후보가 되었기 때문에 가장 왼쪽에 있는 B를 선택했다. 선택된 정점은 주황색 태두리로 표시했다.

 

너비 우선 탐색

선택한 정점 B로 이동한다. 현재 B에 있기 때문에 B가 빨간색으로 바꾸고, 탐색이 끝난 정점은 주황색으로 표시했다.

 

너비 우선 탐색

현재 위치인 B에서 이동할 수 있는 E와 F가 새로운 후보로 추가된다.

 

너비 우선 탐색

현재 후보는 [C, D, E, F]로 가장 먼저 추가된 정점은 C와 D로 그 중 왼쪽에 있는 C를 선택한다.

 

너비 우선 탐색

선택한 정점으로 이동한다.

 

너비 우선 탐색

현재 위치인 C에서 이동할 수 있는 H를 새로운 후보로 추가한다.

목표에 도달하거나 모든 정점에 대한 탐색이 완료될 때 까지 같은 작업을 반복한다.

 

너비 우선 탐색

해당 예시에서는 [A, B, C, D, E, F, H, I, J, K]  순으로 선택한다.

 

너비 우선 탐색

A에서 I까지 탐색한 후 현재 J에 있다.

 

너비 우선 탐색

목표인 G에 도착했으므로 탐색을 종료한다.

 

이처럼 너비 우선 탐색은 시작점에서 가까운 순으로 너비를 넓혀 가며 탐색한다는 특징이 있다. 따라서 목표가 시작점에서 가까이 있을수록 탐색이 빨리 종료 된다.

---

✔️ 추가 내용

너비 우선 탐색을 실시할 때 후보의 정점은 '선입 선출(FIFO)' 구조로 관리하므로 큐(Queue) 데이터 구조를 사용한다.

[자료구조] 큐 (Queue)

 

너비 우선 탐색(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

 

[알고리즘] BFS (Breadth-First Search) : 너비 우선 탐색 알고리즘이란? : olrlobt

https://olrlobt.tistory.com/41