깊이 우선 탐색은 한 경로를 더 진행할 수 있을 때까지 따라간 뒤 돌아와 다른 경로를 조사하는 그래프 탐색이다.
원리
재귀 호출이나 명시적인 스택으로 구현한다. 진입·종료 시점을 구별하면 위상 정렬과 연결 구조 분석에 활용할 수 있다.
그래프 알고리즘 |
|---|
너비 우선 탐색 · 깊이 우선 탐색 · 다익스트라 알고리즘 · 벨만 포드 알고리즘 · 플로이드 워셜 알고리즘 |
예시
폴더 구조를 따라 내려가 자식들을 모두 처리하고 부모로 돌아오는 탐색을 생각할 수 있다. 그래프에서는 순환을 막기 위한 방문 상태가 필요하다.
주의할 점
긴 경로를 재귀로 처리하면 호출 스택 한계에 닿을 수 있다. 스택 구현에서 재귀와 같은 종료 순서가 필요하면 현재 처리할 이웃 위치도 저장한다.