DFS Tree

2020-1학기, 대학에서 ‘알고리즘’ 수업을 듣고 공부한 바를 정리한 글입니다. 지적은 언제나 환영입니다 :)

방향성이 있는 <Directed Graph>를 DFS 방식으로 순위하게 되면, 우리는 방문 순서에 따른 Traversal Tree를 얻게 된다. 이 트리를 이루는 각 vertex 그리고 edge에 이름을 붙이고 분류를 해볼 수 있다!! 한번 살펴보자!!

Terminology.

먼저 vertex에 대한 용어부터 살펴보자. 각 vertex는 <root>, <descendant>, <ancestor>, <parent>, <child> 등의 용어가 있다. 쉬운 개념이라 따로 설명을 하진 않겠다.

다음은 edge 들에 대한 용어를 살펴보자. 먼저 용어를 제시하면, <tree edge>, <forward edge>, <back edge>, <cross edge>가 있다.

먼저 <tree edge>는 말 그대로 DFS tree를 이루는 edge를 말한다.

다음으로 <backward edge>는 DFS 순회 과정에서 해당 edge가 이미 방문한 vertex를 방문하게 만드는 edge 일때, <backward edge>라고 한다. <forward edge>역시 이미 방문한 vertex를 방문하게 만드는 edge지만, 이 경우 그 방향이 (ancestor → descendent) 방향이다. backward edge는 (ancestor ← descendent)니 말 그대로 backwarding 하는 edge인 것이다!

<cross edge>라는 것도 있다. 이 경우, 공통된 ancestor를 가지고 있다면, 이것을 <cross edge>라고 한다.

사실 아래와 같은 공식이 있긴 한데, 본인은 이 공식보다는 (ancestor-descendent) 관계를 바탕으로 edge를 분류하는 편이다. 왜냐하면, 아래의 공식을 쓰면, 본인 기준으로 <cross edge>가 well-define 되지 않는 느낌이 들기 때문이다;; 🤔

---

자 이제 Directed Graph에서 DFS 했을 때, 각 edge를 명명하는 방법을 살펴봤다. 하지만, 이런 의문이 든다.

"왜 vertex와 edge에 이름을 붙였는가?"

그에 대한 답은 <DAG Directed Acyclic Graph>에 있다!! 우리는 Direct Graph가 cycle을 가지는지 판단하기 위해 DFS tree의 edge들을 활용할 수 있다.

Property.

A directed graph has a cycle if and only if its DFS reveals a back edge

즉, 만약 DFS로 Directed Graph를 순회했는데, back edge가 발견된다면 우리는 그 Directed Graph가 DAG가 아님을 알 수 있다!!

DFS는 DAG를 표현하는 데에도 사용할 수 있다!! DAG는 <linearization>이라는 과정을 통해 DAG를 선형의 sequence로 표현할 수 있다!! 이때, 이 선형의 sequence를 DAG를 DFS로 순회하는 순서로 생성한다면, 우리는 이 seq.를 보고 DAG를 복원할 수 있다.