Search Algorithm [2]. 너비 우선 탐색 (Breadth First Search : BFS)

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

너비 우선 탐색 이란?

* 사전적 정의 : 너비 우선 탐색은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.

* 간단한 정의 : 원하는 해를 찾기 위해서 자식노드들을 전부 검사해 나가면서 전진하는 방식

너비 우선 탐색은 말 그대로 너비를 우선적으로 하여 탐색하는 방법을 말한다. 비슷한 탐색 방법으로는 깊이 우선 탐색(Depth First Search : DFS) 가 있는데 이것 역시 말 그래로 깊이를 우선적으로 하여 탐색을 하는 방법을 말한다.

<그림 1>

데이터가 <그림 1> 같은 트리 구조로 되어 있다고 가정을 해보자.

<그림 2>

이때 너비 우선 탐색은 <그림 2>와 같은 방식으로 노드를 탐색한다. 

<그림 2>와 같은 방식을 <그림 1>에 적용시켜 본다면 

[A -> B -> C-> D -> E -> F -> G -> H -> I -> J -> K -> L -> M-> N -> O] 

의 순서로 노드들을 탐색할 것이다.

너비 우선 탐색 의 데이터 저장 구조

너비 우선 탐색은 깊이가 작은 노드들을 우선적으로 검사하면서 검사하는 노드들의 자식노드를 데이터 저장소의 뒷쪽에 추가하면서 데이터를 확장한다.

이때 처음에 들어온 깊이가 작은 노드들에서 새로운 확장을 해 나가기 때문에 First In First Out(FIFO) 의 구조를 발견할 수 있다.

데이터 저장구조에서 First In First Out(FIFO)에 가장 적합한 것은 Queue 구조이다.

따라서 너비 우선탐색을 사용할 때에는 Queue를 저장구조로 사용하는 것이 매우 편리하다.

깊이 우선 탐색 의 탐색 과정 & 데이터 저장 과정

* 아래의 그래프 쉽게 보는 법

- 초록색 점선으로 이루어진 노드는 아직 방문한적도 없고 스택에 들어있지도 않은 노드를 의미

- 실선에 흰색 배경인 노드는 현재 스택에 들어있는 노드를 의미

- 실선에 회색 배경인 노드는 방문한 적이 있는 노드를 의미

- 검은색으로 칠해진 노드는 방문한 적이 있고 그 노드 아래의 자식 노드들까지 전부 방문했음을 의미

(1)	Queue = [A]
(2)	Queue = [B, C]
(3)	Queue = [C, D, E]
(4)	Queue = [D, E, F,G]
(5)	Queue = [E, F, G, H, I]
(6)	Queue = [F, G, H, I, J, K]
(7)	Queue = [G, H, I, J, K, L, M]
(8)	Queue = [H,I,J,K,L,M,N,O]
(9)	Queue = [I, J, K, L, M, N, O]
(10)	Queue = [J, K, L, M, N, O]
(11)	Queue = [K, L, M, N, O]
(12)	Queue = [L, M, N, O]
(13)	Queue = [M, N, O]
(14)	Queue = [N, O]
(15)	Queue = [O]

너비 우선 탐색 의 속성

(d는 데이터 트리 전체 깊이를 의미하고, b는 자식 노드의 개수를 의미한다.)

* 시간 복잡도 (Time Complexity)

트리의 깊이가 목적 노드 깊이와 같을 때 최악의 경우 모든 노드를 다 검사하게 되는데 이때 전체 시간은 아래와 같다.

따라서 너비 우선 탐색의 시간 복잡도는   이다.

* 공간 복잡도 (Space Complexity)

저장 공간에 저장해야할 노드들은 트리에서 현재 검사하고 있는 노드와 깊이가 같은 노드들과 현재 깊이에서 검사를 마친 노드들의 자식노드들이다.

이때 자식노드의 개수는 b이고 최고 깊이가 d이므로 최악의 경우 너비 우선 탐색에서 사용하는 전체 저장 공간은 아래와 같다.

따라서 너비 우선 탐색의 공간 복잡도는  이다.

너비 우선 탐색 의 장단점

* 장점

- 출발 노드에서 목표 노드까지의 최단 길이 경로를 보장할 수 있다.

* 단점

- 경로가 매우 길 경우에는 많은 기억 공간을 필요로 한다.

너비 우선 탐색 의 의사코드(수도코드, Pseudo Code)

Breadth-First-Search(Graph, root):

    

    create empty set S

    create empty queue Q      

    add root to S

    Q.enqueue(root)                      

    while Q is not empty:

        current = Q.dequeue()

        if current is the goal:

            return current

        for each node n that is adjacent to current:

            if n is not in S:

                add n to S

                n.parent = current

                Q.enqueue(n)