방향 그래프에서의 깊이 우선 탐색(DFS)
깊이 우선 탐색(Depth First Search, DFS)은 무방향 그래프와 방향 그래프 모두에 적용할 수 있는 기본적인 그래프 순회 알고리즘입니다. 특히 방향 그래프(Digraph)에서는 DFS를 수행하는 과정에서 간선들을 몇 가지 유형으로 분류할 수 있다는 점이 중요한 특징이며, 이는 사이클 검출이나 위상 정렬 같은 다양한 그래프 문제를 해결하는 핵심 단서가 됩니다.
DFS 알고리즘은 탐색 과정에서 DFS 트리라고 불리는 트리 구조를 형성합니다. 방향 그래프에서 DFS를 수행하면 간선은 다음과 같은 네 가지 유형으로 나눌 수 있습니다.
DFS 간선의 네 가지 유형
트리 간선(Tree Edge, T) – DFS 트리에 실제로 포함되는 간선입니다.
순방향 간선(Forward Edge, F) – 트리 간선과 평행한 방향의 간선으로, 더 작은 DFS 번호에서 더 큰 DFS 번호로 향하고, 더 큰 DFS 완료 번호에서 더 작은 DFS 완료 번호로 향합니다.
역방향 간선(Backward Edge, B) – 더 큰 DFS 번호에서 더 작은 DFS 번호로, 그리고 더 작은 DFS 완료 번호에서 더 큰 DFS 완료 번호로 향하는 간선입니다.
교차 간선(Cross Edge, C) – 더 큰 DFS 번호에서 더 작은 DFS 번호로, 그리고 더 큰 DFS 완료 번호에서 더 작은 DFS 완료 번호로 향하는 간선입니다.
예제로 살펴보기
아래와 같은 방향 그래프가 있다고 가정해 보겠습니다.
정점 A를 시작 정점으로 삼아 DFS를 수행하고, 각 정점에 DFS 번호와 DFS 완료 번호를 기록하면 다음과 같은 DFS 트리가 만들어집니다.
이때 DFS 순회 순서는 A → B → F → D → G → C → E 입니다.
간선 분류 결과
트리 간선(T) : T = {(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}
순방향 간선(F) : F = {(A, G)}
역방향 간선(B) : B = {(G, B)}
교차 간선(C) : C = {(G, D)}
마무리 정리
위 예제에서 볼 수 있듯이, DFS 트리를 분석하면 그래프의 구조적 성질을 명확하게 파악할 수 있습니다. 특히 역방향 간선(Backward Edge)이 하나라도 존재하면 해당 그래프에는 사이클이 존재한다는 것을 의미하므로, 방향 그래프의 사이클 검출 문제에서 DFS 간선 분류는 매우 유용하게 활용됩니다.