목록DFS (1)
DailyCode
깊이 우선 탐색(DFS)
깊이 우선 방식으로 정점을 방문하여 그래프를 탐색하는 그래프 탐색 알고리즘이다. 방문한 각 노드의 부모 노드를 추적하여 소스 노드와 그래프의 다른 노드 사이의 경로를 구성한다. 🚀 알고리즘 논리 DFS는 스택을 사용하여 방문한 노드를 추적한다. 소스 노드에서 시작하여 각 이웃 노드를 탐색하는 방식으로 작동한다. 🏁 알고리즘 동작 과정 시작점을 스택에 추가 스택이 비어있지 않다면, 스택에서 정점을 빼서 이웃 정점을 방문 이웃을 방문한 적이 없는 경우, 방문한 것으로 표시하고 스택에 추가한 후 2단계를 반복 이웃을 방문한 경우, 건너뛰고 2단계를 계속 진행 모든 정점을 방문했다는 것을 나타내는 스택이 비워질 때까지 2~4단계를 반복 (재귀적) ⏲ 시간 복잡도 O(V+E) (V: 노드의 수, E: 그래프의 가..
알고리즘
2023. 6. 12. 14:58