DFS [깊이 우선 탐색] 란?

DFS [깊이 우선 탐색] 란?

그래프 탐색

그래프 탐색 알고리즘 중 대표적으로 사용되는 DFS에 대해 알아보자.

그래프 탐색이란 그래프 내 임의의 한 정점에서 시작해서 모든 정점들을 탐색하는 것을 말한다.

DFS는 현재 정점에서 갈 수 있는 정점까지 들어가면서 탐색하는 것이고, 또 다른 대표적인 그래프 탐색 기법인 BFS는 현재 정점에 연결되어 있는 가까운 정점들부터 차례대로 탐색한다.

DFS (Depth-First Search)

DFS는 깊이 우선 탐색 이라고도 부르는 방법으로 선택한 정점에서 가장 깊게 들어갈 수 있는 부분까지 들어가며 탐색하는 방법이다.

DFS 구현 방법 스택 재귀함수

DFS의 장점과 단점 장점 현 경로상의 노드들만을 기억하므로 저장공간을 적게 사용한다. 목표노드가 깊은 단계에 있는 경우 해를 빠르게 구할 수 있다. 단점 해가 없는 경로에 깊이 빠질 가능성이 있으므로 미리 지정한 임의의 깊이까지만 탐색하고 목표노드를 발견하지 못하면 다음 경로를 따라 탐색하는 방법이 유용할 수 있다. 목표에 이르는 경로가 다수일 경우, DFS는 해에 다다르면 탐색을 끝내버리기 때문에 이 때 얻어진 해는 최단, 최적 경로가 아닐 수 있다.

재귀를 이용한 DFS 구현

bool visited[101] = {}; void dfs(vector graph[], int x) { visited[x] = true; for (int i = 0; i < graph[x].size(); i++) { int y = graph[x][i]; if (!visited[y]) dfs(graph, y); } }

스택을 이용한 DFS 구현

from http://bestinu.tistory.com/12 by ccl(A) rewrite - 2021-07-28 06:26:36