Depth First Search(DFS)

소개

깊이 우선 탐색 - DFS

• 자료구조를 탐색하는 방법 중 하나로 각 가지(branch)를 탐색할 수 있을 수 있는 만큼 최대한 탐색한다.
• 백트래킹(되돌아가 다시 해를 찾음)전에 가지를 최대한 깊게 탐색한다.
  • 즉, 깊이를 우선으로 탐색한다.
• 주로, Graph나 Tree 구조의 자료구조를 탐색한다.

알고리즘의 구현

• DFS는 Stack 자료구조 형태로 구현된다.
• 방문한 node 또는 vertic을 기록해야한다.
  • 한 브랜치에서 더 이상 방문하지 않은 곳이 존재하지 않으면 백트래킹하여 살펴볼 수 있는 브랜치를 찾음
• Recusive function 또는 Stack을 이용하여 구현할 수 있다.
  • DFS 알고리즘은 자기 자신을 호출하는 순환 알고리즘

DFS의 특징

• 전위(pre-order), 후위(post-order), 중위(in-order) 순회 등의 순회 방식은 모두 DFS의 한 종류이다.
• 시간 복잡도가 인접 행렬로 구현된 그래프는 O(N^2), 인접 리스트로 구현된 그래프는 O(N+E)가 걸린다.
  • 단, N는 정점의 수, E는 간선을 의미함

참고

https://en.wikipedia.org/wiki/Depth-first_search
https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/
https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html