Motivation
Coddy의 깊이 우선 탐색 - 그래프 알고리즘 코스 레슨 — 9개 중 2번째.
DFS는 하나의 경로를 선택하여 갈 수 있는 데까지 끝까지 탐색한 후, 탐색하지 않은 이웃이 있는 마지막 정점으로 되돌아오는(백트래킹) 방식으로 그래프를 탐색합니다.
왜 DFS를 배워야 할까요?
- 기초적임: 사이클 감지, 위상 정렬, 연결 요소 및 기타 많은 알고리즘의 근간이 됩니다.
- 단순하고 효율적임: 스택(또는 재귀)과 방문 마커를 사용하여 O(V + E) 시간 복잡도로 실행됩니다.
- 활용도가 높음: 동일한 순회 방식으로 "이 두 정점이 연결되어 있는가?" 또는 "그래프가 몇 개의 분리된 부분으로 구성되어 있는가?"와 같은 질문에 답할 수 있습니다.
결과를 예측 가능하게 유지하기 위해, 우리는 항상 정점의 이웃들을 오름차순으로 방문합니다.
직접 해보기
이 레슨에는 코드 챌린지가 없습니다.
실력 점검이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.
