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

BFS는 너비 우선 탐색(Breadth-First-Search)의 약자이고, DFS와 마찬가지로 그래프의 탐색을 위한 알고리즘이다.

시작 정점에서 가까운 정점을 먼저 방문하고, 멀리 떨어진 정점을 나중에 방문하는 알고리즘이다.

 

즉 , 깊게(deeply) 탐색하는 것이 아닌 넓게(widely) 탐색하는 알고리즘이며 ,

두 노드 사이 최단 경로나 임의의 경로를 알고 싶을 떄 너비 우선 탐색을 선택한다.

 

너비 우선 탐색의 특징

-직관적이지 않은 면이 있다. (시작 노드부터 시작해서 거리에 따라 단계적으로 탐색한다.)

 

-BFS는 재귀적으로 동작하지 않는다.

 

-어떤 정점을 방문했었는지 여부를 반드시 검사해야 한다 ( 그렇지 않으면 무한루프에 빠질 수 있다.)

 

-BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 큐(Queue)를 사용한다.

 

너비 우선 탐색의 동작 과정

 

[출처 : https://developer-mac.tistory.com/64]

1. 처음 시작 노드 방문

 

1을 큐에 삽입하고 , 방문처리를 한다.

queue = [1], visited[1] = true

 

2 큐가 빌 떄까지 계속한다.

 

큐에서 1을 꺼내고(Pop) , 1과 인접한 정점 {2,3,4}를 큐에 삽입하고, 모두 방문처리한다.

queue = [2,3,4] visited = {1,2,3,4}

 

3 큐에서 2를 꺼내고 , 2와 인접한 정점 {5}를 큐에 넣고 방문 처리한다.

 

queue = [3,4,5]  visited = {1,2,3,4,5}

 

4 큐에서 3을 꺼내고 , 3과 인접한 정점 {6,7}을 큐에 넣고 방문 처리한다.

 

queue = [4,5,6,7] visited = {1,2,3,4,5,6,7}

 

5 큐에서 4를 꺼내고 , 4와 인접한 정점 {8}을 큐에 넣고 방문 처리한다.

 

queue = [5,6,7,8] visited = {1,2,3,4,5,6,7,8}

 

6 큐에서 5를 꺼내고 , 5와 인접한 정점 {9}를 큐에 넣고 방문 처리한다.

 

queue = [6,7,8,9] visited = {1,2,3,4,5,6,7,8,9}

 

7 큐에서 6을 꺼내고 , 6과 인접한 정점 {10}을 큐에 넣고 방문 처리한다.

 

queue = [7,8,9,10] visited = {1,2,3,4,5,6,7,8,9,10}

 

8 큐에서 7을 꺼내고 , 방문하지 않은 인접노드가 존재하지 않으므로 큐에 삽입하지 않는다

 

queue = [8,9,10] visited = {1,2,3,4,5,6,7,8,9,10}

 

9 큐에서 8을 꺼내고 , 방문하지 않은 인접노드가 존재하지 않으므로 큐에 삽입하지 않는다

 

queue = [9,10] visited = {1,2,3,4,5,6,7,8,9,10}

 

10 큐에서 9을 꺼내고 , 방문하지 않은 인접노드가 존재하지 않으므로 큐에 삽입하지 않는다

 

queue = [10] visited = {1,2,3,4,5,6,7,8,9,10}

 

11 큐에서 10을 꺼내고 , 방문하지 않은 인접노드가 존재하지 않으므로 큐에 삽입하지 않는다

 

                       -10을 꺼냈을 떄 큐가 비므로 BFS가 종료된다-

 

queue = [] visited = {1,2,3,4,5,6,7,8,9,10}