(Data_Structure) DFS (Depth-First Search)

DFS(Depth-First Search)은 그래프나 트리와 같은 자료 구조에서 사용되는 탐색 알고리즘이다.

하나의 경로를 따라 최대한 깊이 파고들면서 탐색하고 더이상 탐색할 노드가 없을 때 까지 해당하는 경로를 따라간다.

 

DFS는 Stack or Recursion을 사용하여 구현한다.

DFS Algorithm Pseudocode를 보면

Algorithm DFS(G, V)
 Input graph G and a start vertex v of G
 Output labeling of the edges of G
   in the connected component of v
   as discovery edges and back edges
 v.setLabel(VISITED)
 for all e in G.incidentEdges(v)
   if e.getLabel() = UNEXPLORED
     w <- e.opposite(v)
     if w.getLabel() = UNEXPLOreD
       e.setLabel(DISCOVERY)
       DFS(G,w)
     else
       e.setLabel(BACK)

 

 

아래는 그림 진행 순서 예시이다.

 

 

 

DFS는 그래프의 깊이를 우선 탐색하기에 

 

문제) 미로찾기, 경로 찾기, 연결 요소 찾기, 위상 정렬 등에 활용된다.

 

단! 최단 경로 찾기에는 적합하지 않다.