그래프 탐색 기법 리포트

1. 깊이 우선 탐색

깊이 우선 탐색(DFS)은 그래프 이론에서 널리 사용되는 탐색 알고리즘이다. 이 알고리즘은 방문 가능한 모든 정점을 탐색하는 방식으로 작동하며, 먼저 가능한 깊이까지 내려가고, 더 이상 방문할 수 없는 정점에 도달했을 때는 이전 단계로 되돌아가서 다른 경로를 탐색하는 방식이다. DFS는 스택을 활용하여 구현할 수 있으며, 재귀적 호출로도 쉽게 표현될 수 있다. 알고리즘의 기본적인 과정은 다음과 같다. 시작 정점을 선택하고 해당 정점을 방문한 후, 그 정점과 연결된 모든 인접 정점들을 깊이 우선으로 탐색한다. 먼저 하나의 인접 정점으로 이동한 후, 그 정점에서도 같은 과정을 반복한다. 만약 더 이상 탐색할 인접 정점이 없다면, 이전 정점으로 돌아가서 나머지 인접 정점들을 탐색하는 방식이다. 이러한 과정을 통해 최종적으로 모든 정점을 방문하거나 특정 조건을 충족하는 정점을 찾게 된다. DFS는 다양한 데이터 구조에서 구현될 수 있다. 가장 일반적인 구현 방식은 스택을 사용하는 것이다. 스택은 후입선출(LIFO) 구조를 가지므로, 가장 최근에 방문한 정점을 맨 먼저 되돌아가는 방식으로 탐색을 진행할 수 있다. 또한, 재귀 호…