728x90
루트 노드(혹은 다른 임의의 노드)에서 시작해서
다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법
ex) 미로를 탐색할 때, 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면
다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사
- 넓게 탐색하기 전에 깊에 탐색하는 방법
- DFS가 BFS보다 좀 더 간단
- 단순 검색 속도 : 너비 우선 탐색에 비해 느림
사용하는 경우
- 모든 노드를 방문하고자 하는 경우
특징
- 자기 자신을 호출하는 순환 알고리즘 형태
- 전위 순회(Pre-Order Traversals)를 포함한 다른 형태의 트리 순회는 모두 DFS의 한 종류*
- 어떤 노드를 방문했었는지 여부를 반드시 검사해야 함.
(이를 검사하지 않는 경우, 무한 루프에 빠질 위험이 있음.💥🔃☠️)
시간 복잡도
N : 정점의 수
E : 간선의 수
- 인접 리스트로 표현된 그래프 : O(N + E)
- 인접 행렬로 표현된 그래프 : $O(N^2)$
희소 그래프(Spare Graph) : 그래프 내에 적은 숫자의 간선만을 가지는 그래프
이 경우, 인접 행렬보다 인접 리스트를 사용하는 것이 유리
cf. (반의어) 밀집 그래프(dense graph) : 간선의 수가 최대 간선의 수에 가까운 그래프
🏷️ 참고한 블로그
728x90
