[Algorithm] BFS(너비우선탐색)와 DFS(깊이우선탐색)

 

그래프 탐색

그래프의 각 정점을 방문하는 것을 탐색이라고 한다.

하나의 정점으로부터 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다.

탐색에서 노드의 방문 순서에 따라 방법이 나누어진다. 

두 가지 방법: BFS, DFS

 

 

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

https://www.youtube.com/watch?v=66ZKz-FktXo

정의: 특정한 데이터를 탐색할 때 너비를 우선으로 하여 탐색을 수행하는 탐색 알고리즘, 즉 시작점이 있을 때 시작점과 가까운 것 위주로 탐색하겠다는 것

특징

- 큐(=먼저 들어온 것을 먼저 처리, 선입선출)를 사용한다.

- 맹목적인 탐색을 하고자 할 때 사용할 수 있는 탐색 기법이다.

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

- 흔히 미로 찾기와 같은 알고리즘에서 많이 이용한다

- 비슷한 알고리즘: Prim, Dijkstra

방법

1. 큐에서 하나의 노드를 꺼낸다

2. 해당 노드에 연결된 노드 중 방문하지 않은 노드를 방문하고, 차례대로 큐에 삽입한다.

3. 반복

 

 

깊이 우선 탐색(Depth First Search) ,DFS

https://www.youtube.com/watch?v=l0Rsu7dziws

정의: 맹목적으로 각 노드를 탐색할 때 사용, 루트 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색한다.

특징

- 넓게 탐색하기 전에 깊게 탐색하는 것

- 스택을 사용하고, 스택을 사용하지 않아도 구현이 가능하다는 특징이 있다.

- 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문, 재귀 함수 이용(순환 알고리즘 형태)

- 깊이 우선 탐색이 너비 우선 탐색보다 간단하다.

- 검색 속도는 너비 우선 탐색에 비해서 느리다.

 

방법

1. 스택의 최상단 노드를 확인한다

2. 최상단 노드에게 방문하지 않은 인접 노드가 있다면 그 노드를 스택에 넣고 방문 처리한다. 지 않은 인접 노드가 없으면 스택에 최상단 노드를 뺀다.

3. 반복

 

 

참고

gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

[알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog