타임스탬프 깊이 우선 탐색 편집하기

타임스탬프 깊이 우선 탐색(DFS with Timestamps)은 DFS 수행 중 노드 방문 및 완료 시점을 기록하는 기법이다. 각 노드는 DFS가 처음 도달한 시간과 탐색이 끝난 시간을 기록하며, 이 정보를 이용해 위상 정렬, 사이클 검출, 강한 연결 요소 분할(SCC) 등에 활용할 수 있다.
==개요==
DFS 탐색 중 각 노드는 두 개의 타임스탬프를 가진다.
*'''d[u] (탐색 시작 시간, Discovery time)''' - DFS가 처음 해당 노드를 방문한 시점.
*'''f[u] (탐색 종료 시간, Finish time)''' - 해당 노드의 모든 인접 노드 탐색이 끝난 시점.
타임스탬프를 사용하면 그래프의 구조를 분석하는 여러 가지 중요한 정보를 얻을 수 있다.
*노드의 '''위상 관계'''를 확인할 수 있다.
*'''사이클 검출'''이 가능하다.
*DFS 트리에서 간선을 분류하는 기준이 된다.
==타임스탬프를 활용한 DFS 구현==
각 노드마다 타임스탬프를 기록하고 간선을 분류한다.<syntaxhighlight lang="python">
class TimeStampDFS:
    def __init__(self, graph):
        self.graph = graph  # Adjacency list representation of graph
        self.clock = 1
        self.first_time = {v: 0 for v in graph}  # Initialize firstTime[v] = 0
        self.last_time = {v: 0 for v in graph}   # Initialize lastTime[v] = 0
        self.parent = {v: None for v in graph}  # Parent tracking
        self.edge_types = {}  # Dictionary to store edge classifications

    def DRIVER_INIT(self):
        """ Initialize the global variables before starting DFS """
        self.clock = 1
        for v in self.graph:
            self.parent[v] = None
            self.first_time[v] = 0
            self.last_time[v] = 0
        self.edge_types.clear()

    def INIT(self, v):
        """ Assign first timestamp when visiting a node """
        self.first_time[v] = self.clock
        self.clock += 1

    def PREVISIT(self, v, u):
        """ Implementing PREVISIT(v, u) exactly as given in the document """
        if self.first_time[v] == 0:  # (T1) First time visiting v → Tree Edge
            self.edge_types[(u, v)] = "Tree Edge"
            self.parent[v] = u
            self.first_time[v] = self.clock
            self.clock += 1
        elif self.first_time[v] > self.first_time[u]:  # (T2) Forward Edge
            self.edge_types[(u, v)] = "Forward Edge"
        elif self.last_time[v] == 0:  # (T3) Back Edge (Cycle)
            self.edge_types[(u, v)] = "Back Edge"
        else:  # (T4) Cross Edge
            self.edge_types[(u, v)] = "Cross Edge"

    def POSTVISIT(self, v):
        """ Assign last timestamp when finishing a node """
        self.last_time[v] = self.clock
        self.clock += 1

    def DFS(self, v):
        """ Perform DFS with timestamp tracking """
        self.INIT(v)
        for neighbor in self.graph[v]:
            self.PREVISIT(neighbor, v)  # Edge classification occurs here
            if self.first_time[neighbor] == self.clock - 1:  # Check if neighbor was just seen
                self.DFS(neighbor)
        self.POSTVISIT(v)

    def DFS_Driver(self):
        """ Driver function to ensure all nodes are visited """
        self.DRIVER_INIT()
        for v in self.graph:
            if self.first_time[v] == 0:  # Equivalent to checking if v is unseen
                self.DFS(v)

    def print_timestamps(self):
        """ Display the first and last timestamps for each node """
        print("\nDFS Timestamps:")
        for v in sorted(self.graph.keys()):  # Sorting to keep order consistent
            print(f"{v}: first_time={self.first_time[v]}, last_time={self.last_time[v]}")

    def print_edges(self):
        """ Display the edge classifications """
        print("\nEdge Classification:")
        for (u, v), edge_type in self.edge_types.items():
            print(f"{u} → {v}: {edge_type}")

# Example usage:
G = {
    "A": ["B", "D"],
    "B": ["C", "E"],
    "C": ["F"],
    "D": ["H"],
    "E": ["A", "H"],
    "F": ["I"],
    "G": ["D"],
    "H": ["G","F","I"],
    "I": ["H"]
}

dfs = TimeStampDFS(G)
dfs.DFS_Driver()
dfs.print_timestamps()
dfs.print_edges()
</syntaxhighlight>
==타임스탬프를 이용한 간선 분류==
DFS 수행 중 각 간선(u → v)은 타임스탬프 관계를 이용해 다음과 같이 분류할 수 있다.
{| class="wikitable"
|+DFS 간선 분류 기준
|-
!간선 종류!!조건
|-
|'''트리 간선(Tree Edge)'''||조상에서 자손으로 향하는 간선으로, 아래가 아닌 모든 경우 (부모 - 자신간의 직접 간선이 됨)

* firstTime[v] = 0 
* 목적지를 처음 방문하는 경우
|-
|'''역방향 간선(Back Edge)'''||자손에서 조상으로 역행하는 간선

* lastTime[v] = 0
* 목적지가 아직 처리(done)되지 않은 경
|-
|'''순방향 간선(Forward Edge)'''||조상에서 자손으로 향하는 간선이지만 세대를 건너뛴 경우 (Tree Edge인 경우 Forward Edge가 아님)

* 트리 간선이 아니면서, 
* firstTime[v] > firstTime[u] 
* u의 방문이 먼저 이루어진 경우 u → v 는 순방향이다.
|-
|'''교차 간선(Cross Edge)'''||두 간선이 그래프에 속하는 간선이지만 조상 자손 관계가 없는 경우

* 그 외의 경우 (소스코드 참조)
|}
===예제===
[[파일:일방향 그래프 예시.png]]

위 소스코드상의 그래프이다. 소스코드를 실행하면 아래와 같이 계산된다.<syntaxhighlight>
📌 DFS Timestamps:
A: first_time=1, last_time=26
B: first_time=3, last_time=25
C: first_time=5, last_time=21
D: first_time=15, last_time=16
E: first_time=23, last_time=24
F: first_time=7, last_time=20
G: first_time=13, last_time=17
H: first_time=11, last_time=18
I: first_time=9, last_time=19

📌 Edge Classification:
A → B: Tree Edge
B → C: Tree Edge
C → F: Tree Edge
F → I: Tree Edge
I → H: Tree Edge
H → G: Tree Edge
G → D: Tree Edge
D → H: Back Edge
H → F: Back Edge
H → I: Back Edge
B → E: Tree Edge
E → A: Back Edge
E → H: Cross Edge
A → D: Forward Edge
</syntaxhighlight>
==타임스탬프 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²)
==같이 보기==
*[[깊이 우선 탐색]]
*[[위상 정렬]]
*[[강한 연결 요소]]
*[[사이클 검출]]