깊이 우선 탐색(DFS)

DFS란?

• 그래프에 대한 철저한 검색 기술 중 하나입니다.
  
  
• 스택 데이터 구조를 사용하여 재귀 함수로 구현할 수 있습니다.
  
  
• 시간 복잡도는 O(노드 수 + 에지 수)입니다.
  
  

DFS 수행 방법

DFS 과정

1. 스택의 후입선출 속성을 사용하여 DFS 순회를 표현할 수 있습니다.
   
   
2. DFS를 시작할 노드를 결정하고 스택 데이터 구조를 초기화합니다.
   
   (DFS 프로세스 1)
3. 방문 목록이 스택 데이터 구조에 추가됨과 동시에 방문 기록이 남습니다.
   
   
4. 스택에서 초기화된 노드를 제거하고 제거된 노드 옆에 있는 노드를 다시 스택에 추가합니다.
   
   
5. 마찬가지로 방문기록을 방문목록에 남겨 재방문을 방지합니다.
   
   
6. 스택 데이터 구조에 더 이상 값이 없을 때까지 반복합니다.
   
   
7. 위의 구조를 반복하여 DFS의 검색 순서를 검사합니다.