DFS(깊이 우선 탐색) 인접 행렬 구현 (JAVA)
그래프 이론의 가장 기본적인 탐색기법인 DFS는 현재 정점과 연결된 다른 정점으로 깊이를 우선하여 탐색하는 알고리즘이다. 간단한 그래프 하나를 예로 들어보자면, 다음과 같은 그래프가 있고 1번 정점에서 탐색을 시작한다고 가정할때 1 >> 2 >> 4 >> 7 >> 8 >> 3 >> 5 >> 6 의 순서로 방문하여 탐색하는것을 말한다. 보다 자세한 과정을 설명하자면 다음과 같이 진행된다. 1. 현재 정점을 스택에 삽입, 방문처리 2. 스택의 top에 해당하는 정점과 연결된 정점중 방문하지 않은 정점 현재 정점으로 취급 3. 1,2 반복수행 >> 현재 연결된 정점들이 모두 방문처리 된경우 스택 pop 4 . 스택이 비워질때 까지 반복수행 이와 같이 스택을 활용하여 깊이 우선 탐색을 진행시킨다. 이때 컴퓨터는..
알고리즘/구현
2023. 9. 3. 14:41