1. DFS

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

루트 노드(혹은 다른 임의의 노드)에서 시작해서 특정 분기를 완벽하게 실행한 후,

다음 분기로 넘어가는 방식

 

 

 

 

DFS의 특징

- 재귀(Recursion)방식으로 순환호출 / 스택을 사용하는 방법으로 이루어지며, 어떤 노드를 방문하였는지 여부를 꼭 확인해주어야 한다 (안그러면 무한루프)

 

DFS 시간복잡도

- 인접 리스트 : O(N + E)

- 인접 행렬 : O(N^2)