Algorithm

알고리즘 - 깊이 우선 탐색

안중환 2015. 11. 13. 13:11

- DFS (Depth First Search)

- 재귀, 스택을 사용하여 구현 가능

스택을 이용하여 부모노드로 되돌아오는 과정을 백트래킹(backtracking)이라 한다.

- visited 정보 필요

-  시간복잡도
  : 정정의 수 n, 간선의 수 e
  : 인접 리스트 

  : 인접 행렬