Editing 타임스탬프 깊이 우선 탐색

타임스탬프 깊이 우선 탐색(DFS with Timestamps)은 DFS 수행 중 노드 방문 및 완료 시점을 기록하는 기법이다. 각 노드는 DFS가 처음 도달한 시간과 탐색이 끝난 시간을 기록하며, 이 정보를 이용해 위상 정렬, 사이클 검출, 강한 연결 요소 분할(SCC) 등에 활용할 수 있다.
==개요==
DFS 탐색 중 각 노드는 두 개의 타임스탬프를 가진다.
*'''d[u] (탐색 시작 시간, Discovery time)''' - DFS가 처음 해당 노드를 방문한 시점.
*'''f[u] (탐색 종료 시간, Finish time)''' - 해당 노드의 모든 인접 노드 탐색이 끝난 시점.
타임스탬프를 사용하면 그래프의 구조를 분석하는 여러 가지 중요한 정보를 얻을 수 있다.
*노드의 '''위상 관계'''를 확인할 수 있다.
*'''사이클 검출'''이 가능하다.
*DFS 트리에서 간선을 분류하는 기준이 된다.
==타임스탬프를 활용한 DFS 구현==
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
==타임스탬프를 이용한 간선 분류==
DFS 수행 중 각 간선(u → v)은 타임스탬프 관계를 이용해 다음과 같이 분류할 수 있다.
{| class="wikitable"
|+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 트리 간의 간선)
|}
===예제===
아래 그림에서 DFS 수행 시각을 기록하면:<syntaxhighlight>
        A (1,12)
       /    \
  (2,7) B    C (8,11)
     /   \       \
(3,4) D  E (5,6)  F (9,10)

</syntaxhighlight>타임스탬프를 이용한 간선 분석:
{| class="wikitable"
|+ 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)
|}
==타임스탬프 DFS의 활용==
'''위상 정렬(Topological Sorting)'''
*DFS 종료 시간이 큰 노드부터 정렬하면 위상 정렬 결과를 얻을 수 있음.
'''사이클 검출'''
*역방향 간선(Back Edge)이 존재하면 사이클이 있음.
'''강한 연결 요소(SCC) 찾기'''
*타잔 알고리즘(Tarjan’s Algorithm) 또는 코사라주 알고리즘(Kosaraju's Algorithm)에서 활용됨.
==DFS의 시간 복잡도==
DFS의 시간 복잡도는 그래프의 정점(V)과 간선(E)의 개수에 따라 결정된다.
*'''인접 리스트(Adjacency List)'''로 구현한 경우: O(V + E)
*'''인접 행렬(Adjacency Matrix)'''로 구현한 경우: O(V²)
==같이 보기==
*[[깊이 우선 탐색]]
*[[위상 정렬]]
*[[강한 연결 요소]]
*[[사이클 검출]]