먼저 내려가고 돌아오기
현재 정점의 아직 방문하지 않은 이웃으로 이동하고, 그곳에서도 같은 과정을 반복한다. 더 진행할 곳이 없으면 이전 단계로 돌아와 남은 이웃을 살핀다. 어떤 이웃을 먼저 고르는지에 따라 방문 순서는 달라질 수 있다.
순환에서 무한 반복 막기
그래프에는 이전에 방문한 정점으로 돌아오는 간선이 있을 수 있다. 방문 상태를 저장하지 않으면 같은 부분을 계속 탐색할 수 있다. 발견한 상태와 처리를 마친 상태를 구분하면 순환 검사 등에도 활용할 수 있다.
재귀와 스택의 관계
재귀 구현은 호출 스택에 돌아올 위치를 저장한다. 같은 흐름을 직접 만든 스택으로 표현할 수도 있다. 경로가 매우 깊다면 재귀 호출의 깊이 제한을 고려해야 하며, 구현 방식이 같지 않아도 탐색의 기본 원리는 유지된다.
최단 경로와 구분하기
깊이 먼저 진행한다고 목표를 가장 적은 간선으로 찾는 것은 아니다. 한 경로가 길게 이어져도 먼저 탐색할 수 있기 때문이다. 연결 관계 분석과 방문 순서, 진입 및 종료 정보를 얻는 목적과 최단 거리 계산을 구분해야 한다.
관련 문서
너비 우선 탐색 / 스택 / 재귀 / 그래프 (자료 구조) / 알고리즘