[Data Structure] 트리(Tree)와 그래프(Graph) 이해하기

인트로

그래프 탐색 알고리즘인 BFS, DFS와 트리 탐색 알고리즘인 전위 중위 후위 순회를 정리하기 전에

배경지식인 트리와 그래프의 관계 그리고 특징을 정리하려 한다. 

(좌) 트리          (우) 그래프

결론부터 말하면 트리는 특정 조건을 만족하는 그래프이다.

즉, 트리는 그래프이지만 그래프는 트리가 아니다.

 

그래프(Graph)

그래프는 현실에 존재하는 개체 간의 관계를 표현하는 하나의 표기법일 뿐이다. 

 

현실에서도 그래프를 찾아볼 수 있으며 흔히 보는 지하철 노선도가 그래프이다.

기흥이라는 점이 개체, 기흥과 강남대를 이어주는 선이 관계이다.

 

컴퓨터공학적인 시선으로 그래프를 바라보면 개체는 노드(Node)로, 관계는 간선(Edge)으로 표현된다. 

그래프도 여러 종류가 존재한다. 대표적으로

1) 무방향 그래프 (Undirected Graph)

무방향 그래프는 양쪽 모두 이어진 방향성이 없는 그래프이다.

A와 B가 연결되어 있으면 B와 A도 연결되어 있는 의미로 노드들이 대칭적인 관계가 형성된다.

2) 방향 그래프

방향 그래프는 간선에 방향이 존재하는 그래프이다.

A에서 C로 향하는 간선이 존재하더라도 C에서 A로 향하는 간선은 없을 수 있다.

이처럼 간선에 방향이 존재하다 보니 비 대칭적인 관계가 형성된다.

 

여기서 한 가지 중요한 개념이 등장하게 되는데 바로 사이클(Cycle)이다.

사이클이란 시작 정점과 끝나는 정점이 동일한 경로를 말한다. 

아래의 그림에선 A - D - A와 A - C - B - A가 사이클이다. 

 

참고로 사이클이 존재하지 않는 방향 그래프는 DAG(Directed Acyclic Graphs)라고 불리며 트리는 반드시 사이클이 없는 DAG 여야 한다.

 

3) 가중치 그래프

가중치 그래프란 간선에 가중치(비용)가 추가된 그래프이다.

가중치 방향 그래프를 예시로 들어보면 A 정점에서 D 정점으로 가려면 4만큼의 비용이 필요하며 D에서 A로 가기 위해선 2만큼의 비용이 필요하다.

 

 

트리(Tree)

이제는 트리를 살펴보자.

현실에서도 트리를 찾아볼 수 있으며 회사의 조직도가 바로 트리의 대표적인 예시이다.

그래프는 개체 간의 "관계"를 표현한다면 트리는 개체를 "계층"구조로 표현한다. 

 

 

앞서 언급했던 것처럼 트리는 특정 조건을 만족하는 그래프이며 트리의 특징을 살펴보자.

 

[※ 트리(Tree) ※]

1) 최상위 루트(Root) 노드(A)가 존재하며 루트 노드를 시작으로 부모(A)와 자식(B, C) 관계가 형성된다. 

2) 자식 노드는 한 개의 부모 노드만을 가진다.

3) 두 정점 사이에 반드시 한 개의 경로(단방향)를 가지며 부모에서 자식으로 연결된 Top to Bottom 형식이 일반적이다.

4) 트리는 절대 사이클을 형성해선 안 된다.

5) 트리의 탐색 알고리즘으로 전위 중위 후위 순회가 있다.

6) 트리의 종류로 이진트리, 이진 탐색 트리, 완전 이진트리, 힙트리가 있다.

마치며

가볍게 개념은 정리했으니 이제 예시 코드가 포함된 글을 작성하려 합니다.

언제가 될진 모르겠지만 좋은 예제로 다시 찾아뵙겠습니다.