1. BFS(Breath-Find-Search) : 너비 우선 탐색

BFS(Breath-Find-Search)

너비 우선 탐색

 

그래프의 탐색 방법 중 하나의 BFS에 대해서 살펴보려고 한다.

BFS는 말 그대로 너비 우선 탐색, 즉 특정 Vertice에서 가장 가까운 Vertice부터 탐색한다는 뜻이다.

 

우선 BFS를 사용하기 위해서는 Queue가 필요하다.

 

Stack, Queue, Heap에 대해서는 나중에 자세히 설명하기로 하고

Queue에 대해 간단하게 설명하자면 FIFO(First in First out - 선입선출)으로 동작하는 자료구조이다.

 

위에서도 말했듯이 BFS의 가장 큰 개념은 가까운 정점을 방문하되, 아직 방문하지 않은 정점인 경우 방문 리스트에 정점을 저장하면 된다. 이 방문 리스트가 우리가 원하는 최종적인 BFS의 탐색 순서이다. 알고리즘 동작 방식은 다음과 같다.

1. Queue에서 특정 정점을 뺀다.

2. 특정 정점이 아직 방문하지 않은 정점인 경우 이를 방문처리 해준다.

3. 이 정점과 연결된 다른 정점을 Queue에 넣는다.

 

다음과 같은 그래프가 주어졌을 때 BFS를 적용해보자.

 

 

① 시작 정점을 8이라고 가정하자. Queue에는 시작 정점이 들어있다.

Queue	8
Visit

 

② Queue에서 8을 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

이후 8과 연결된 1과 2를 Queue에 넣어준다.

Queue	1	2
Visit	8

 

③ Queue에서 1을 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

이후 1과 연결된 5와 3을 Queue에 넣어준다. (Queue에 넣어줄 때 오름차순으로 정렬한다고 가정)

Queue	2	3	5
Visit	8	1

 

④ Queue에서 2를 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

이후 2와 연결된 6을 Queue에 넣어준다.

Queue	3	5	6
Visit	8	1	2

 

⑤ Queue에서 3를 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

3과 연결된 다른 정점이 없으므로 넘어간다.

Queue	5	6
Visit	8	1	2	3

 

⑥ Queue에서 5를 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

이후 5와 연결된 7과 9를 Queue에 넣어준다.

Queue	6	7	9
Visit	8	1	2	3	5

 

⑦ Queue에서 6을 빼주고 아직 방문하지 않은 정점이므로, 이를 방문처리 해준다.

이후 6과 연결된 4를 Queue에 넣어준다.

Queue	7	9	4
Visit	8	1	2	3	5	6

 

⑧ 위 과정을 Queue에 원소가 없을 때까지 반복한다. 과정이 종료되면 Visit에 저장된 정점의 순서가 BFS이다.

Queue
Visit	8	1	2	3	5	6	7	9	4

 

BFS는 최단거리를 탐색하는 경우에 사용된다. 미로찾기에서 사용될 수 있다.

 

위의 개념을 파이썬으로 구현해보았다.

 

위에서 언급한 그래프로 입력 값을 주면 이론상으로 구한 답과 동일한 것을 볼 수 있다.

 

[Input]

9 8 8  # 정점의 개수, 간선의 개수, 시작 정점
8 1
8 2
1 5
1 3
5 7
5 9
2 6
6 4

 

[Output]

 

충남대학교 컴퓨터공학과 이영석 교수님의 알고리즘 수업과 동빈나의 유튜브 강좌(youtu.be/66ZKz-FktXo)를 참고했습니다.