스택5 [알고리즘] DFS c++ 구현 및 설명 목차 dfs의 정의 및 특징 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법을 말한다. 그래프의 정점을 발견하는 가장 단순하고 고전적인 방법이다. bfs보다는 비교적 구현이 간단하다. dfs 구현 시 시간 복잡도 인접 리스트: O(V +E) 1 2 3 4 3 4 2 3 4 5 1 이런식으로 각 노드마다 길이가 달라 O(V +E)시간이 걸린다. 희소한 그래프일 시 추천하는 방법이다. 인접 행렬: O(V^2) x 1 2 3 4 5 1 1 1 1 1 1 2 0 1 1 0 1 3 0 0 1 1 0 4 0 1 0 1 1 5 1 0 0 1 1 이런식으로 노드의 관계를 나타내 주어 O(V^2) 시간이 걸린다. 조밀한 그래프일 시 추천하는 방법이다. dfs의 구현 나는 재귀적인 방.. 2024. 2. 7. 이전 1 2 다음 728x90
