타임스탬프 깊이 우선 탐색

타임스탬프 깊이 우선 탐색(DFS with Timestamps)은 DFS 수행 중 노드 방문 및 완료 시점을 기록하는 기법이다. 각 노드는 DFS가 처음 도달한 시간과 탐색이 끝난 시간을 기록하며, 이 정보를 이용해 위상 정렬, 사이클 검출, 강한 연결 요소 분할(SCC) 등에 활용할 수 있다.

1 개요

DFS 탐색 중 각 노드는 두 개의 타임스탬프를 가진다.

• d[u] (탐색 시작 시간, Discovery time) - DFS가 처음 해당 노드를 방문한 시점.
• f[u] (탐색 종료 시간, Finish time) - 해당 노드의 모든 인접 노드 탐색이 끝난 시점.

타임스탬프를 사용하면 그래프의 구조를 분석하는 여러 가지 중요한 정보를 얻을 수 있다.

• 노드의 위상 관계를 확인할 수 있다.
• 사이클 검출이 가능하다.
• DFS 트리에서 간선을 분류하는 기준이 된다.

2 타임스탬프를 활용한 DFS 구현

time = 0  # 전역 변수로 타임스탬프 관리

def dfs_with_timestamps(graph, node, state, d, f):
    global time
    state[node] = "seen"  # 방문 시작
    time += 1
    d[node] = time  # 탐색 시작 시간 기록

    for neighbor in graph[node]:
        if state[neighbor] == "unseen":
            dfs_with_timestamps(graph, neighbor, state, d, f)

    state[node] = "done"  # 탐색 완료
    time += 1
    f[node] = time  # 탐색 종료 시간 기록

# 그래프 표현 (인접 리스트)
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': [],
    'F': []
}

# 초기화
state = {node: "unseen" for node in graph}
d = {}  # 탐색 시작 시간
f = {}  # 탐색 종료 시간

# DFS 수행
for node in graph:
    if state[node] == "unseen":
        dfs_with_timestamps(graph, node, state, d, f)

# 결과 출력
print("탐색 시작 시간:", d)
print("탐색 종료 시간:", f)

3 타임스탬프를 이용한 간선 분류

DFS 수행 중 각 간선(u → v)은 타임스탬프 관계를 이용해 다음과 같이 분류할 수 있다.

DFS 간선 분류 기준

간선 종류	조건
트리 간선(Tree Edge)	d[u] < d[v] && v가 처음 방문된 노드 (새로운 DFS 트리 분기)
역방향 간선(Back Edge)	d[v] < d[u] && f[u] < f[v] (조상 노드로 돌아가는 간선, 사이클 존재)
순방향 간선(Forward Edge)	d[u] < d[v] && f[v] < f[u] (자손 노드로 향하는 간선)
교차 간선(Cross Edge)	f[v] < d[u] (다른 DFS 트리 간의 간선)

3.1 예제

아래 그림에서 DFS 수행 시각을 기록하면:

        A (1,12)
       /    \
  (2,7) B    C (8,11)
     /   \       \
(3,4) D  E (5,6)  F (9,10)

타임스탬프를 이용한 간선 분석:

DFS 수행 과정 및 간선 분류

단계	방문한 노드	탐색 시작 시간	탐색 종료 시간	부모 노드	간선 유형
1	A	1	12	-	-
2	B	2	11	A	Tree Edge (A → B)
3	D	3	4	B	Tree Edge (B → D)
4	E	5	10	B	Tree Edge (B → E)
5	C	6	7	A	Tree Edge (A → C)
6	F	8	9	C	Tree Edge (C → F)
7	E → C	-	-	E	Back Edge (E → C) (사이클 검출)
8	F → B	-	-	F	Cross Edge (F → B)

4 타임스탬프 DFS의 활용

위상 정렬(Topological Sorting)

• DFS 종료 시간이 큰 노드부터 정렬하면 위상 정렬 결과를 얻을 수 있음.

사이클 검출

• 역방향 간선(Back Edge)이 존재하면 사이클이 있음.

강한 연결 요소(SCC) 찾기

• 타잔 알고리즘(Tarjan’s Algorithm) 또는 코사라주 알고리즘(Kosaraju's Algorithm)에서 활용됨.

5 DFS의 시간 복잡도

DFS의 시간 복잡도는 그래프의 정점(V)과 간선(E)의 개수에 따라 결정된다.

• 인접 리스트(Adjacency List)로 구현한 경우: O(V + E)
• 인접 행렬(Adjacency Matrix)로 구현한 경우: O(V²)

6 같이 보기

• 깊이 우선 탐색
• 위상 정렬
• 강한 연결 요소
• 사이클 검출