DFS (1) 썸네일형 리스트형 [Algorithm] DFS 1. DFS (Depth First Search, 깊이 우선 탐색) 그래프 탐색 방법 중의 하나로 시작 노드로 부터 탐색을 진행할 때 해당 분기 (branch)에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다. 분기를 완벽하게 탐색한다는 것은 해당 노드에 대해서 깊이를 우선적으로 탐색한다는 의미이다. 그래프의 임의의 한 정점으로부터 연결되어 있는 한 정점으로만 우선 탐색한다. 더이상 연결되어 있지 않을 때까지 탐색하고 다시 되돌아가서 탐색하지 않은 방향의 정점, 분기로 탐색을 진행한다. 모든 정점을 방문할 때까지 탐색을 반복한다. DFS는 자기 자신을 반복해서 호출하는 순환 알고리즘의 형태를 가지고 있다. 트리 탐색에서의 depth-first traversal (preorder tr.. 이전 1 다음