dfs

Depth First Search (DFS) - 깊이 우선 탐색

비선형 구조인 그래프 구조는 그래프로 표현된 모든 자료를 빠짐없이 검색하는 것이 중요하다. 이러한 탐색 방법에는 대표적으로 Depth First Search (깊이 우선 탐색) 그리고 Breadth First Search (너비 우선 탐색)이 있다. 우선 DFS 부터 알아보도록 하겠다. 1. DFS 로직 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳 까지 깊이 탐색 더 이상 갈 곳이 없게 되면 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아옴 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하여 순회 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용한다 2. 스택을 사용한 DFS 알고리즘 설명 정점 v에 ..