DFS1 [JAVA] 깊이 우선 탐색 (DFS) 깊이 우선 탐색은 한 그래프의 정점들을 유용한 순서로 방문하는 한 방법이다 주어진 그래프의 한 정점에서 탐색을 시작하여 그 정점을 방문했다고 표시하고, 그 정점에 인접한 정점들 중 방문 안한 정점을 임의로 선택하여 방문한다 선택된 정점에 대해 같은 탐색과정을 반복한다. 더 이상 방문하지않은 인접한 정점이 없으면 바로 전에 방문했던 정점으로 돌아간다. 탐색을 반복하다가 시작 정점으로 돌아간 후 그 시작 정점에 인접한 정점들 중 방문하지 않은 정점이 없으면 종료한다. 시간복잡도 - 인접 행렬: O(V^2) - 인접 리스트: O(V+E) 알고리즘 알고리즘 DFSearch(G) 1 V에 있는 각 정점을 '방문 안함'으로 표시한다. 2 각 정점 v에 대해 v가 '방문 안함'으로 표시되어 있다면 DFS(v)를 호출.. 2021. 12. 12. 이전 1 다음