깊이 우선 탐색: 한 갈래를 끝까지 따라간 뒤 돌아오기
깊이 우선 탐색은 현재 정점의 한 이웃으로 내려가고, 더 갈 곳이 없으면 이전 정점으로 돌아와 다른 갈래를 탐색한다. 재귀 호출이나 명시적 스택으로 아직 끝나지 않은 탐색 상태를 보존한다. 그래프에서 단순히 재귀만 사용하면 사이클 때문에 같은 정점을 계속 방문할 수 있어 방문 기록이 필요하다.
점선은 새로운 간선이 아니라 탐색 후 되돌아가는 동작을 나타낸다.
시작과 종료를 구분하면 보이는 정보
정점 상태를 미발견, 진행 중, 완료로 나누면 탐색의 구조를 더 많이 알 수 있다. 진행 중은 그 정점이 현재 호출 경로에 있다는 뜻이다. 방향 간선의 끝이 진행 중 정점이라면 현재 경로를 거슬러 가는 사이클이 존재한다.
다음 코드는 방향 그래프의 사이클 존재를 판단하는 재귀 예다. 모든 정점이 graph의 키로 등록되어 있다고 가정한다.
def has_directed_cycle(graph):
state = {vertex: 0 for vertex in graph}
def visit(vertex):
state[vertex] = 1
for neighbor in graph[vertex]:
if state[neighbor] == 1:
return True
if state[neighbor] == 0 and visit(neighbor):
return True
state[vertex] = 2
return False
return any(state[v] == 0 and visit(v) for v in graph)
A→B→C→A에서는 C가 진행 중인 A를 발견하여 사이클을 알 수 있다. 반면 이미 완료된 정점으로 가는 간선이 있다는 사실만으로 사이클이라고 판단할 수는 없다. 상태 한 종류만 저장하면 이 차이를 놓칠 수 있다.
방문 순서는 목적에 따라 달라진다
정점을 내려갈 때 기록하는 전위 순서와 모든 자식을 마친 뒤 기록하는 후위 순서는 서로 다르다. 후위 종료 순서는 DAG의 위상 정렬이나 강한 연결 요소 분석에 활용된다. 트리에서는 자식을 모두 처리한 결과를 부모에서 합칠 때도 후위가 자연스럽다.
인접 리스트 DFS의 시간은 O(V+E), 방문 정보는 O(V)다. 재귀 스택은 최악 O(V)까지 깊어질 수 있다. 균형 트리에서 짧게 끝났다고 일반 그래프에서도 안전한 깊이라고 가정할 수 없다.
명시적 스택으로 바꾸면 언어의 재귀 한도를 피할 수 있다. 다만 정점만 스택에 넣는 간단한 구현은 재귀의 종료 시점과 같은 정보를 바로 주지 않는다. 후위 처리가 필요하면 다음에 볼 이웃 위치나 진입·종료 사건도 저장해야 한다.
무방향 그래프의 사이클 검사는 부모로 되돌아가는 간선을 구별해야 한다. 방향 그래프용 규칙을 그대로 쓰면 정상적인 양방향 간선을 사이클로 오해할 수 있다. DFS는 틀보다 방문 상태의 의미와 그래프 조건이 정확성을 결정한다.
탐색 중 이웃 목록을 수정하면 순회 규칙이 달라질 수 있다. 변경 가능한 그래프에서 DFS를 실행할 때는 고정된 스냅샷을 쓰거나 변경의 허용 범위를 정해야 한다.