Time and Space Complexity
Coddy의 너비 우선 탐색 - 그래프 알고리즘 코스 레슨 — 9개 중 7번째.
시간 복잡도:
- O(V + E)
- 모든 정점은 한 번씩 큐에 삽입(enqueue) 및 삭제(dequeue)되며, 각 간선은 일정한 횟수만큼 검사됩니다.
공간 복잡도:
- O(V + E)
- 인접 리스트는 모든 간선을 저장하며, 큐와 방문 배열(visited array)은 최대 V개의 정점을 보유합니다.
요약:
- BFS는 큐를 사용하여 계층별로 탐색하며, 먼 정점보다 가까운 정점을 먼저 방문합니다.
- 이러한 계층적 순서 덕분에 가중치가 없는 그래프에서 최단 경로를 찾는 데 가장 적합한 알고리즘입니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
너비 우선 탐색 - 그래프 알고리즘의 모든 레슨
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity