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

Related to: Algorithms

개요

임의의 정점(vertax)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법. 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.

핵심 개념

• 탐색 방식: 한 경로를 끝까지 탐색한 후 다른 경로로 이동 (깊이 우선)
• 구현 방식: 재귀 또는 명시적 스택(Stack) 사용
• 시간 복잡도: $O(V+E)$ (V: 정점 수, E: 간선 수)
• 공간 복잡도: $O(V)$ (스택 깊이 기준)

관련 개념

• Algorithm
• Graph
• 그래프와 트리(Tree and Graph)
• Tree

참조

https://ko.wikipedia.org/wiki/깊이_우선_탐색https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html