Time and Space Complexity
Coddy의 깊이 우선 탐색 - 그래프 알고리즘 코스 레슨 — 9개 중 7번째.
시간 복잡도:
- O(V + E)
- 인접 리스트를 구축할 때 모든 간선을 한 번씩 거치며, 탐색 과정에서 모든 정점을 방문하고 각 간선을 일정한 횟수만큼 확인합니다.
공간 복잡도:
- O(V + E)
- 인접 리스트는 모든 간선을 저장하며, 방문 배열(visited array)과 스택은 각각 최대 V개의 정점을 보관합니다.
요약:
- DFS는 먼저 깊게 탐색하며, 방문하지 않은 이웃 노드가 없으면 역추적(backtracking)합니다.
- 선형 시간에 실행되며 많은 그래프 알고리즘의 근간이 됩니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
깊이 우선 탐색 - 그래프 알고리즘의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity