깊이 우선 탐색(depth-first search: DFS)

DFS는 탐색기법의 하나로, 트리인 경우 아래처럼 말단 노드까지 쭉 내려가본 다음, 다시 올라오면서(back track) 안가본 노드를 가보는 식으로 동작한다.

동작기법이 재귀호출과 유사하여, 재귀로 많이 구현하는 편

재귀를 사용하는 경우 시스템 스택의 제한을 받아서 탐색공간이 너무 크면 stack overflow가 발생할 수 있는 단점이 있다.

시간복잡도

V개의 정점, E개의 간선으로 이루어진 그래프의 경우에..

여기에 잘 나와있는데, 인접행렬로 구현했을 경우 다음 간선으로 가는데 V루프를 돌리므로, 시간복잡도는 $O(V^2)$이 되고(E에 상관없음에 주의),

인접리스트로 구현할 경우 랜덤액세스 형식으로 다음 간선으로 접근하므로 $O(V+E)$가 된다. (근데 간선이 굉장히 많은 경우는 $E \sim V^2$개 근처까지 가므로 이때는 $O(V+V^2) = O(V^2)$ 이렇게 되기는 한다.)

그래서 인접리스트로 구현하는게 인접행렬보다 좋은 어프로치다.