타임스탬프 깊이 우선 탐색

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

1 개요

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

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

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

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

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

각 노드마다 타임스탬프를 기록하고 간선을 분류한다.

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()

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

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

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)	두 간선이 그래프에 속하는 간선이지만 조상 자손 관계가 없는 경우 그 외의 경우 (소스코드 참조)

3.1 예제

위 소스코드상의 그래프이다. 소스코드를 실행하면 아래와 같이 계산된다.

📌 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

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 같이 보기

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