토픽 35 / 66·그래프 자료구조

DFS (Depth-First Search)

그래프의 한 정점에서 시작하여 가능한 깊이 끝까지 탐색한 후 백트래킹하는 그래프 순회 알고리즘으로, 스택 또는 재귀로 구현

목적: 그래프 순회, 경로 탐색, 사이클 검사, 위상 정렬, 연결 요소

특징: 깊이 우선, 스택/재귀, 백트래킹, 메모리 효율(경로 길이만큼)

동작

구현: 재귀(암묵적 스택) 또는 명시적 스택

시간 복잡도: O(V + E) - 인접 리스트, O(V²) - 인접 행렬

공간 복잡도: O(V) - 방문 배열 + O(h) - 스택(h = 깊이)

장점: 메모리 효율(경로만), 구현 간단(재귀), 백트래킹, 경로 저장

단점: 최단 경로 보장 안됨, 무한 루프 위험(사이클), 깊은 그래프에서 스택 오버플로우

적용사례

비교: DFS(깊이/스택/메모리효율/경로) vs BFS(너비/큐/최단경로)

연관: 그래프, BFS, 백트래킹, 위상 정렬, 재귀