[알고리즘/이론]깊이 우선 탐색(DFS)

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다.

너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다.

검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 수 있으며 따라서 깊이 우선 포레스트를 형성한다고 한다.

너비 우선 검색과 같이 발견 여부, 인접 정점 조사 여부를 표시하여 트리들의 정점이 중복되지 않도록 한다.

깊이 우선 검색을 할 때는 발견한 시간, 인접 정점을 조사한 시간을 정점의 속성으로 기록하여 그래프의 구조에 대한 정보를 얻을 수 있다. 이 시간은 1이상 2*V이하의 시간을 가지며 이는 V개의 정점에 대해 1번씩 발견, 인접 정점을 조사하기 때문이다. 당연히 발견 시간은 인접 정점 조사 시간보다 빠르며 이 시간들을 경계로 정점의 상태 여부가 달라진다.

깊이 우선 탐색은 보통 재귀함수를 통해 구현된다. 여러 간선 중 1개에 연결된 정점을 루트로 하는 트리의 모든 정점을 검색한 다음 옆의 간선으로 넘어가 똑같은 검색을 반복하는 식으로 작동한다.

---

DFS의 수행시간

DFS의 정점 초기화, 깊이 우선 포레스트 형성을 하는 데 Θ(V)만큼의 시간이 소모된다. 트리를 방문하는 데는 총 Θ(E)가 소모된다. 방문하지 않은 정점에 대해 1번 방문하고, 방문 여부를 표시하기 때문에 정확히 모든 정점에 대해 1번 방문하기 때문이다. 따라서 총 수행시간은 Θ(V+E)가 된다.

---

깊이 우선 검색의 특성

그래프의 구성에 대한 정보를 확인할 수 있습니다. 재귀함수의 호출에 따라 깊이 우선 트리가 생성되며, 최종적으로 깊이 우선 포레스트를 형성하게 됩니다.

또한, 발견 시간과 조사 시간이 괄호의 형태를 띄게 됩니다.

---

정리 1(괄호)

u, v가 서로 자손이 아니거나, u가 v의 자손이거나, v가 u의 자손이다.

따름 정리 1

v가 u의 자손이면, u의 발견시간<v의 발견시간<v의 종료시간<u의 종료시간이며 그 역도 성립한다.

정리 2

v가 u의 자손이면 u의 발견시간에는 u에서 v까지 정점이 흰색이다. 그 역도 성립한다.

---

간선의 분류

트리 간선(tree edge) – 깊이 우선 포레스트에 있는 간선이다.

역행 간선(back edge) - 깊이 우선 트리에서 한 정점에서 조상으로 가는 간선이다. 자기 순환 간선도 역행 간성으로 생각한다.

순행 간선(forward edge) - 깊이 우선 트리에서 한 정점에서 자손으로 가는 트리 간선이 아닌 간선이다.

교차 간선(cross edge) - 이외의 모든 간선을 일컫는다. 같은 깊이 우선 트리에 있는 경우 하나의 정점이 조상이 아니어야 하며, 다른 깊이 우선 트리 간의 간선일 수도 있다.

DFS 알고리즘을 통해 간선의 종류를 구분할 수 있다. 정점을 탐색할 때 마주치는 정점이 방문하지 않은 정점이라면 트리 간선을 의미하며, 방문한 정점이라면 역행 간선을 나타낸다. 종료된 정점이라면 순행 혹은 교차 간선을 나타낸다.

무방향 그래프의 경우 검색에서 처음 마주치는 것에 따라 간선을 분류한다. 이때 순행과 교차 간선은 발생하지 않는다고 한다.