DFS Algorithm (Depth-First-Search, 깊이 우선 탐색)

• DFS (깊이 우선 탐색)

 

그래프

  : 하나의 정점으로부터 시작, 차례대로 모든 정점들을 한 번씩 방문하는 것.

 

DFS (Depth-First-Search, 깊이 우선 탐색)

  : 루트 노드 (or 다른 임의의 노드)에서 시작해서

    다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법.

     ex) 미로 탐색 시 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 이전의 갈림길로 돌아와서 다른 방향으로 다시 탐색.

    

     => 즉, 넓게(wide) 탐색하기 전에 깊게 (deep) 탐색.

          모든 노드를 방문하고자 하는 경우에 선택하는 방법.

         

 

 

• DFS의 과정

 

출처 : https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html

 

1. 시작 노드 A 방문 (방문 표시)

 

2. A와 인접한 노드 차례로 방문

 

3. A와 인접한 노드 B의 이웃 노드들도 모두 방문

 

4. B의 분기를 완벽하게 방문, 탐색했다면

A로 다시 돌아가 아직 방문 되지 않은 A의 이웃 노드들 방문

 

5. 방문 되지 않은 정점이 없으면 종료

 

 

 

• DFS의 특징

 

     •순환 알고리즘의 형태

     •그래프 탐색의 경우, 어떤 노드의 방문 여부를 반드시 검사해야 함

         검사 x => 무한 루프에 빠질 위험 有

참고 : https://coding-factory.tistory.com/611

 

 

 

• DFS의 시간 복잡도

 

DFS는 그래프의 모든 간선을 조회, 방문, 탐색. (N: 노드 수, E: 에지 수)

 

시간 복잡도

    •인접 행렬로 표현된 그래프 => O(N^2)

    •인접 리스트로 표현된 그래프 => O(N+E)

 

      희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리

         -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프