[Algorithm] 그래프의 깊이 우선 탐색(Depth-first search)

1. 서론

그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘들을 그래프의 탐색 알고리즘이라 한다. 트리의 순회는 사실 트리에 있는 정점들을 모두 확인한다는 것 외에 큰 의미가 없었지만, 그래프는 트리보다 구조가 훨씬 복잡할 수 있기 때문에 탐색 과정에서 얻어지는 정보가 아주 중요하다. 탐색 과정에서 어떤 간선이 사용되었는지, 또 어떤 순서로 정점들이 방문되었는지를 통해 그래프의 구조를 알 수 있다. 탐색 알고리즘 중 가장 널리 사용되는 두 가지가 깊이 우선 탐색과 너비 우선 탐색이다.

깊이우선 탐색은 그래프의 모든 정점을 발견하는 가장 단순하고 고전적인 방법이다. (작성중...)