트리와 그래프

Q. 트리, 그래프를 비교하여 설명해주실 수 있을까요?

그래프

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

트리

트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다. 그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다. 부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.