[기초 알고리즘] 넓이 우선 탐색(BFS)Ⅰ

넓이 우선 탐색(BFS)

그래프의 탐색에는 넓이 우선 탐색과 깊이 우선 탐색 두 가지로 나뉩니다.

오늘은 넓이 우선 탐색을 먼저 공부를 해봤습니다.

넓이 우선 탐색은 Breadth First Search의 약자입니다.

시작점을 기준으로 동일한 거리에 있는 노드들을 먼저 탐색하는 탐색 기법입니다.

그렇다면 왜? 넓이 우선 탐색이라고 부를까요?

탐색이 시작되면 깊이 우선 탐색과 다르게 동일 선상에 있는 노드들을 탐색하게되고 또 그 노드들을 기준으로 

동일한 거리에 있는 노드들을 탐색하게 됩니다. 

그렇게 되면 탐색 범위가 점점 넓어 지는 듯한 모양을 띄게 됩니다.

그래서 넓이 우선 탐색이라고 부르게 되었다고 합니다.

그렇다면 이제 기본적인 것들을 알아보겠습니다.

• 거리(Distance)

거리는 간단하게 말해서 정점 사이에 있는 간선의 수를 말합니다.

* 최단 경로에 있는 간선의 수

ex) 정점 A 와 정점 C의 거리는 2가 됩니다.

• 넓이 우선 탐색(Breadth First Search)

지정된 시작점으로 부터 도달 가능한 모든 간선을 탐색하는 과정을 말합니다.

시작점으로 부터 거리를 하나씩 늘리면서 정점을 발견하게 됩니다.

1) 거리가 1인 정점을 찾는다(B, D)

2) 거리가 2인 정점을 찾는다(C)

이러한 과정을 거치면서 모든 정점을 찾는 것입니다.

이 과정에서 시작점에서의 거리 / 바로 직전 정점(Predecessor vertax)가 필요합니다.

시작점에서의 거리

말 그대로 시작점에서 현재 내가 탐색하고 있는 정점까지의 거리를 말합니다.

예를 들어 정점 E는 거리가 3이 됩니다. ( E.d = 3 )

바로 직전 정점

바로 직전 정점은 내가 탐색하고 있는 정점의 바로 전에 탐색한 정점을 말합니다.

예를 들어 정점 E의 바로 직전 정점은 C가 됩니다. ( E.π = C )

괄호 안에 있는 것은 표현 방법입니다. 

자! 이제 기본적인 내용을 학습 했으니 어떤 순서로 탐색이 되는지 알아 볼께요