이 블로그의 "그래프에 관하여" 시리즈의 첫 번째 카테고리, ❮DFS 트리❯의 개요이다. DFS 트리는 DFS를 응용한 다양한 알고리즘들을 이해하기 위한 좋은 표현법이자 도구이다. 조금 어려운 감이 있지만 꼼꼼히 이해한다면 큰 도움이 될 것이라고 생각한다. DFS 트리/포레스트란? 어떤 연결 그래프에서 DFS 순회하는 과정을 그렸을 때 나타나는 유향 신장 트리(directed spanning tree)를 DFS 트리라고 한다. 당연히 여러 개가 존재할 수 있다. 연결 그래프가 아닐 경우에는 각 연결 컴포넌트마다 DFS 트리를 만들 수 있으니 DFS 포레스트로 확장해서 생각할 수 있다. 유향 그래프일 경우, DFS 트리의 간선들을 네 가지로 분류할 수 있다. 트리 간선(tree edge): DFS 트리에 ..