[알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS)

 

그래프

 

정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다.

G = (V,E)

 

출처 : https://velog.io/@sohi_5/algorithmDFS

세 가지 그림 모두 그래프이다. 트리 또한 그래프 중 하나이며

정점과 간선의 관계에 따라 세부적으로 구분할 수 있다.

 

 

그래프 탐색

 

그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것이다.

깊이 우선 탐색과 너비 우선 탐색은 그래프를 탐색하는 방법 중 하나이다.

 

 

깊이 우선 탐색

: DFS (Depth-First Search)

 

최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동.

루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다.

 

모든 노드를 방문하고자 하는 경우 깊이 우선 탐색이 적합하다.

너비 우선 탐색과 비교하여 구현은 간단하지만 검색 속도는 느리다.

 

자기 자신을 호출하는 순환 알고리즘의 형태를 지닌다.

스택을 사용하여 구현한다.

 

 

출처 : https://yunyoung1819.tistory.com/86

 

 

너비 우선 탐색

: BFS (Breadth-Frist Search)

 

루트 노드에서 시작하여 인전합 노드를 먼저 탐색하는 방법

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.

 

주로  두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 사용한다.

깊이 우선 탐색과는 달리 재귀적으로 동작하지 않고 큐를 이용하여 구현한다.

 

출처 : https://yunyoung1819.tistory.com/86

 

DFS, BFS 특징에 따라 사용에 더 적합한 문제들이 있다.

 

1. 그래프의 모든 정점을 방문하는 문제

편한 것을 사용하면 된다.

 

2. 경로의 특징을 저장해둬야 하는 문제

DFS를 주로 사용한다.

 

3. 최단 거리 구해야 하는 문제

BFS가 유리하다. 

DFS 경로에 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있다.