반응형 깊이 우선 탐색1 탐색 알고리즘 - 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색이란? - 임의의 노드에서 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 것. - 순환 알고리즘의 형태 - 그래프 탐색 시 방문 노드를 반드시 검사해야 한다. - 스택 또는 재귀를 이용하여 구현한다. 깊이 우선 탐색 방법 - 1. A노드를 방문하고, 방문한 노드를 표시한다. - 2. A노드와 인접한 B노드를 방문하고, 방문한 노드를 표시한다. - 3. B노드와 인접한 C노드를 방문하고, 방문한 노드를 표시한다. - 4. C노드와 인접한 노드가 없는 경우, 다시 B노드로 돌아가서 다른 인접한 노드가 있는지 탐색한다. - 5. 위 과정을 반복하여 모든 노드를 탐색한다. 깊이 우선 탐색 코드(C++) - 1. 재귀 이용 #incl.. 2020. 6. 22. 이전 1 다음 반응형
