[알고리즘] dfs(깊이 우선 탐색, 시간 복잡도, 사용하는 곳, 특징, 구현방법)

개념

그래프 내에서 시작 정점 부터 원하는 정점까지 이동가능한지 알아보는 알고리즘이다

하나의 분기에 도달했다면 그 분기에 대해서는 탐색할 수 있는 모든 경로를 탐색하고 넘어가는 알고리즘이다

 

사용하는 곳

A에서 B로의 이동 가능 여부

전자회로에서 연결 여부

 

시간 복잡도

인접 행렬의 경우 O(n^2)

인접 리스트의 경우 O(n+m)

 

구현방법

백트래킹을 사용해 구현한다

 

특징

너무 깊을 경우에는 모든 정점을 다 깊게 탐색하므로 다른 알고리즘을 사용하는것이 현명하다