깊이 우선 탐색
깊이 우선 탐색은 한 경로를 가능한 깊이까지 탐색한 다음 이전 분기점으로 되돌아간다 그래프 알고리즘의 그래프 탐색 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 사이클을 가진 그...
| 분류 | 알고리즘 · 그래프 알고리즘 · 그래프 탐색 |
|---|---|
| 문제 | 한 경로를 가능한 깊이까지 탐색한 다음 이전 분기점으로 되돌아간다 |
| 입력 | 사이클을 가진 그래프에서는 이미 방문한 정점의 재탐색을 제어해야 한다 |
| 핵심 단계 | 재귀 호출 또는 명시적 스택을 사용해 방문하지 않은 이웃으로 진행한다 |
| 시간 복잡도 | O(V+E) |
| 공간·구현 | 인접 리스트에서 O(V+E), 스택과 방문 배열 O(V) |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
깊이 우선 탐색은 한 경로를 가능한 깊이까지 탐색한 다음 이전 분기점으로 되돌아간다 그래프 알고리즘의 그래프 탐색 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 사이클을 가진 그래프에서는 이미 방문한 정점의 재탐색을 제어해야 한다.[1]
핵심 절차는 재귀 호출 또는 명시적 스택을 사용해 방문하지 않은 이웃으로 진행한다. 진입·종료 순서와 방문 상태를 저장하면 사이클, 위상 순서와 연결 요소를 판단할 수 있다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 인접 리스트에서 O(V+E), 스택과 방문 배열 O(V) 정점 수를 V, 간선 수를 E라고 나타낼 때 O(V+E)의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
위상 정렬·강한 연결 요소·단절점 탐색의 기반이다. 너비 우선 탐색과 달리 일반적인 비가중 최단 경로를 보장하지 않는다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]