DFS

BFS와 같이 그래프 탐색의 한 종류이다.

 

DFS : Depth-first search 깊이 우선 탐색 이라고 한다.

 

DFS는 스택으로 구현이 가능하고 재귀로도 구현이 가능하다.

 

 

DFS 동작 방식은

 

1 - 2 - 3 - 4 - 6 - 5 과 같이 동작한다.

 

---

재귀함수 

- 자기 자신을 다시 호출하는 함수

 

- 주의 할점

 - 재귀 함수가 종료되는 시점이 반드시 명시되어야한다.

 - 재귀함수의 깊이가 너무 깊어지면 스택 오버플로우 현상이 발생한다.

 

- DFS, 백트래킹에서 주로 사용

 

아이디어

 

- 시작점에 연결된 Vertex 찾기

 

- 연결된 Veertex를 계속해서 찾음

 

- 더이상 연결된 Vertex 없을경우 다음

 

시간 복잡도

 

- 시간복잡도란? : 알고리즘이 얼마나 오래걸리는지 나타내는것

 

-DFS : O(V+E)