[알고리즘] Depth-First Search

DFS(깊이우선탐색)

features

• 스택 사용 (재귀 호출 스택 / 명시적 스택)
• 가장 최근에 발견된 정점의 인접 간선들을 계속 탐색 (→ 깊이 우선)
• 어떤 정점 v의 모든 간선을 다 보면, predecessor로 되돌아가(backtrack) 남은 간선 탐색
• 한 컴포넌트 내에서 갈 수 있는 한 최대한 깊게 내려감
• 그래도 아직 white 정점이 남아 있으면, 그중 하나를 골라 다시 DFS-Visit 시작 → DFS forest

input and output

• Input: G = (V,E), directed or undirected. !No source vertex given
  //V is set of vertices, E is set of Edges

• Output: d[v] = discovery time (v turns from white to gray)
  f[v] = finishing time (v turns from gray to black)
  파이[v] = predecessor of v = u, such that v was discovered during the u's adjacency list
  

• Uses the same Coloring scheme for v as BFS
  white=0
  gray=1
  black=2

Pseudo Code

DFS(G)
	for each vertex u in V[G]
    	do color[u] <-white
        	파이[u] <-NULL
    time <- 0
    for each vertex u in V[G]
    	do if color[u] = white
        	then DFS-Visit(u)
DFS-Visit(u)
	color[u] <- GRAY
    #white vertex u has been discovered
    time <-time+1
    d[u] <- time
    for each v in adjacency[u]
    	do if color[v] = white
        	then 파이[v] <- u
            	DFS-Visit(v)
    color[u] <- black
    #blacken u, it is finished
    f[u] <- time <- time+1

Total Running Time

Loops on lines 1-2 and 5-7 take O(V) time, excluding time to execute DFS-Visit

DFS-Visit is called once for each white vertex v in V when it’s painted gray the first time. Lines 3-6 of DFS-Visit is executed |Adj[v]| times. The total cost of executing DFS-Visit is sigma v in V |Adj[v]| = O(E)

so
if V>=E then O(V)
else if V<=E then O(V+E)