타임스탬프 깊이 우선 탐색: Difference between revisions

From CS Wiki
(새 문서: 타임스탬프 깊이 우선 탐색(DFS with Timestamps)은 DFS 수행 중 노드 방문 및 완료 시점을 기록하는 기법이다. 각 노드는 DFS가 처음 도달한 시간과 탐색이 끝난 시간을 기록하며, 이 정보를 이용해 위상 정렬, 사이클 검출, 강한 연결 요소 분할(SCC) 등에 활용할 수 있다. ==개요== DFS 탐색 중 각 노드는 두 개의 타임스탬프를 가진다. *'''d[u] (탐색 시작 시간, Discovery time)''' - DFS...)
 
No edit summary
 
Line 9: Line 9:
*DFS 트리에서 간선을 분류하는 기준이 된다.
*DFS 트리에서 간선을 분류하는 기준이 된다.
==타임스탬프를 활용한 DFS 구현==
==타임스탬프를 활용한 DFS 구현==
<syntaxhighlight lang="python">
각 노드마다 타임스탬프를 기록하고 간선을 분류한다.<syntaxhighlight lang="python">
time = 0  # 전역 변수로 타임스탬프 관리
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 dfs_with_timestamps(graph, node, state, d, f):
    def DRIVER_INIT(self):
    global time
        """ Initialize the global variables before starting DFS """
    state[node] = "seen"  # 방문 시작
        self.clock = 1
    time += 1
        for v in self.graph:
    d[node] = time  # 탐색 시작 시간 기록
            self.parent[v] = None
            self.first_time[v] = 0
            self.last_time[v] = 0
        self.edge_types.clear()


     for neighbor in graph[node]:
     def INIT(self, v):
         if state[neighbor] == "unseen":
        """ Assign first timestamp when visiting a node """
            dfs_with_timestamps(graph, neighbor, state, d, f)
         self.first_time[v] = self.clock
        self.clock += 1


     state[node] = "done"  # 탐색 완료
     def PREVISIT(self, v, u):
    time += 1
        """ Implementing PREVISIT(v, u) exactly as given in the document """
    f[node] = time # 탐색 종료 시간 기록
        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):
graph = {
        """ Assign last timestamp when finishing a node """
     'A': ['B', 'C'],
        self.last_time[v] = self.clock
    'B': ['D', 'E'],
        self.clock += 1
     'C': ['F'],
 
     'D': [],
     def DFS(self, v):
    'E': [],
        """ Perform DFS with timestamp tracking """
    'F': []
        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):
state = {node: "unseen" for node in graph}
        """ Display the edge classifications """
d = {} # 탐색 시작 시간
        print("\nEdge Classification:")
f = {} # 탐색 종료 시간
        for (u, v), edge_type in self.edge_types.items():
            print(f"{u} {v}: {edge_type}")


# DFS 수행
# Example usage:
for node in graph:
G = {
     if state[node] == "unseen":
    "A": ["B", "D"],
        dfs_with_timestamps(graph, node, state, d, f)
    "B": ["C", "E"],
    "C": ["F"],
    "D": ["H"],
     "E": ["A", "H"],
    "F": ["I"],
    "G": ["D"],
    "H": ["G","F","I"],
    "I": ["H"]
}


# 결과 출력
dfs = TimeStampDFS(G)
print("탐색 시작 시간:", d)
dfs.DFS_Driver()
print("탐색 종료 시간:", f)
dfs.print_timestamps()
dfs.print_edges()
</syntaxhighlight>
</syntaxhighlight>
==타임스탬프를 이용한 간선 분류==
==타임스탬프를 이용한 간선 분류==
Line 57: Line 105:
!간선 종류!!조건
!간선 종류!!조건
|-
|-
|'''트리 간선(Tree Edge)'''||d[u] < d[v] && v가 처음 방문된 노드 (새로운 DFS 트리 분기)
|'''트리 간선(Tree Edge)'''||조상에서 자손으로 향하는 간선으로, 아래가 아닌 모든 경우 (부모 - 자신간의 직접 간선이 됨)
 
* firstTime[v] = 0
* 목적지를 처음 방문하는 경우
|-
|-
|'''역방향 간선(Back Edge)'''||d[v] < d[u] && f[u] < f[v] (조상 노드로 돌아가는 간선, 사이클 존재)
|'''역방향 간선(Back Edge)'''||자손에서 조상으로 역행하는 간선
 
* lastTime[v] = 0
* 목적지가 아직 처리(done)되지 않은 경
|-
|-
|'''순방향 간선(Forward Edge)'''||d[u] < d[v] && f[v] < f[u] (자손 노드로 향하는 간선)
|'''순방향 간선(Forward Edge)'''||조상에서 자손으로 향하는 간선이지만 세대를 건너뛴 경우 (Tree Edge인 경우 Forward Edge가 아님)
 
* 트리 간선이 아니면서,
* firstTime[v] > firstTime[u]  
* u의 방문이 먼저 이루어진 경우 u → v 는 순방향이다.
|-
|-
|'''교차 간선(Cross Edge)'''||f[v] < d[u] (다른 DFS 트리 간의 간선)
|'''교차 간선(Cross Edge)'''||두 간선이 그래프에 속하는 간선이지만 조상 자손 관계가 없는 경우
 
* 그 외의 경우 (소스코드 참조)
|}
|}
===예제===
===예제===
아래 그림에서 DFS 수행 시각을 기록하면:<syntaxhighlight>
[[파일:일방향 그래프 예시.png]]
        A (1,12)
      /    \
  (2,7) B    C (8,11)
    /  \      \
(3,4) D  E (5,6)  F (9,10)


</syntaxhighlight>타임스탬프를 이용한 간선 분석:
위 소스코드상의 그래프이다. 소스코드를 실행하면 아래와 같이 계산된다.<syntaxhighlight>
{| class="wikitable"
📌 DFS Timestamps:
|+ DFS 수행 과정 및 간선 분류
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
| 1 || A || 1 || 12 || - || -
E: first_time=23, last_time=24
|-
F: first_time=7, last_time=20
| 2 || B || 2 || 11 || A || Tree Edge (A → B)
G: first_time=13, last_time=17
|-
H: first_time=11, last_time=18
| 3 || D || 3 || 4 || B || Tree Edge (B D)
I: first_time=9, last_time=19
|-
 
| 4 || E || 5 || 10 || B || Tree Edge (B E)
📌 Edge Classification:
|-
A → B: Tree Edge
| 5 || C || 6 || 7 || A || Tree Edge (A C)
B → C: Tree Edge
|-
C F: Tree Edge
| 6 || F || 8 || 9 || C || Tree Edge (C F)
F → I: Tree Edge
|-
I → H: Tree Edge
| 7 || E → C || - || - || E || Back Edge (E → C) (사이클 검출)
H G: Tree Edge
|-
G → D: Tree Edge
| 8 || F B || - || - || F || Cross Edge (F → B)
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의 활용==
==타임스탬프 DFS의 활용==
'''위상 정렬(Topological Sorting)'''
'''위상 정렬(Topological Sorting)'''

Latest revision as of 21:27, 7 March 2025

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

1 개요[edit | edit source]

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

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

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

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

2 타임스탬프를 활용한 DFS 구현[edit | edit source]

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

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 타임스탬프를 이용한 간선 분류[edit | edit source]

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 예제[edit | edit source]

일방향 그래프 예시.png

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

📌 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의 활용[edit | edit source]

위상 정렬(Topological Sorting)

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

사이클 검출

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

강한 연결 요소(SCC) 찾기

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

5 DFS의 시간 복잡도[edit | edit source]

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

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

6 같이 보기[edit | edit source]