반응형 [C++로 배우는 알고리즘과 자료구조] Day 23: 깊이 우선 탐색 (DFS) 깊이 우선 탐색 (DFS, Depth-First Search)깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 가능한 한 깊게 탐색한 후 더 이상 깊이 갈 수 없으면 다시 되돌아와 다른 경로를 탐색하는 방식입니다. DFS는 스택 자료구조를 사용하여 구현할 수 있으며, 재귀적으로도 구현이 가능합니다.DFS의 주요 특징:시간 복잡도: (O(V + E)), 여기서 (V)는 정점의 수, (E)는 간선의 수입니다.공간 복잡도: (O(V)), 재귀 호출 스택의 깊이입니다.DFS 구현그래프 구현 (인접 리스트 사용)#include #include #include // 그래프 클래스 정의class Graph {public: Graph(int vertices); void addEdge(int v, .. 2024. 8. 1. 이전 1 다음 반응형
