[JS] 깊이 우선 탐색

1. 깊이 우선 탐색 깊이 우선 탐색(DFS, Depth First Search)은 시작 정점에서 한 방향으로 갈 수 있는 가장 먼 경로까지 깊이 탐색해나가다가 더 이상 갈곳이 이 없으면 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서, 다른 방향의 간선으로 탐색을 계속함으로써 모든 정점을 방문하는 순회 방법이다. 저번에 트리에 대해 포스팅했을 때 전위, 중위, 후위 순회 방법 세 가지를 언급한 적이 있었다. 이 세 가지 방법이 깊이 우선 탐색에 해당된다. 깊이 우선 탐색은 마지막에 만났던 갈림길 간선의 정점으로 가장 먼저 되돌아가 다시 깊이 우선 탐색을 반복해야 하므로 스택을 사용한다. 2. 탐색 과정 그림을 이용해서 알고리즘이 어떻게 돌아가는지 설명해보도록 하겠다. 밑에 [그림1]은 빈 스택과..

2020.06.22