[알고리즘]너비 우선 탐색(BFS)

너비우선탐색

 

BFS는 컴퓨터 알고리즘 분야에서 2가지 알고리즘의 약자이며, 의학 분야에서 근육이 마구 연축하는 병증(Benign Fasciculation Syndrome)을 이르는 약자이기도 하다.

이 너비 우선 탐색은 먼저 가까운 정점부터 시작하여 가장 먼 정점까지 방문하기 시작합니다.

깊이 우선 탐색은 스택을 통하여 재귀 호출을 이용한 반면에, 너비 우선 탐색은 방문한 정점의

위치를 기억하기 위해 큐를 이용합니다.너비 우선 탐색은 예를 들면, 위에서 말한대로와 같이

깊이를더해가며 방문을 하며 찾으려는 데이터를 찾거나, 더 이상 방문할 곳이 존재하지 않으면

탐색을 마칩니다.

방문 순서는 '1 -> 2 -> 3 -> 4 -> 5 -> 6' 임을 알 수 있습니다.

여기서는 1이 시작점이라고 가정합니다. 우선은 큐가 어떻게 되고,

어떻게 저런 순서가 나올 수 있는지 과정을 모두 살펴보도록 합시다.

 

 

 

 

 

(1) 깊이 0은 정점 1밖에 존재하지 않으니 정점 1에서 시작합니다. 큐에는 1이 들어갑니다

(2)깊이 1은 정점 3인 존재하며, 큐에서 2를 빼고 2와 인접ㅂ한 4,5를 삽입합니다.

(3)깊이 2는 정점 2와 정점 3이 존재하며, 큐에서 1을 빼고 2와 3을 삽입합니다.

(4)그리고 큐에서 3을 빼면, 3과 인접한 6을 큐에 삽입합니다. 4는 이미 방문된

상태이므로 탐색할 필요가 없습니다.

(5)큐에서 4를 빼는데, 이 때 4와 인접한 정점인 2,3,5,6은 이미 방문된 상태이므로

탐색할 필요가 없습니다.(즉, 큐에 삽인할 정점이 존재하지 않느다는 겁니다.)

(6)큐에서 5를 빼는데, 이때 5와 인접한 정점인 2,4,6은 이미 방문된 상태이므로 탐색할

필요가 없습니다.

(7)큐에서 6을 빼는데, 이때 6과 인접한 정점인 3,4,5는 이미 방문된 상태이므로 탐색할

필요가 없습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

---

저의 블로그 봐주셔서 감사합니다

재.미.있.게 보셧다면 아래 하트 ❤(공감) 과 댓글 부탁 드려요 .

다들 코로나 극복 화이팅