그래프(Graph)와 트리(Tree)

그래프(Graph)란 무엇인가?

그래프

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료구조이다.

이를 통해 연결된 노드 간의 관계를 표현할 수 있다.

 

그래프의 특징

• 그래프는 순환 혹은 비순환 구조를 이룬다.
• 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.
• 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.
• 2개 이상의 경로가 가능하다. (무방향, 방향, 양방향 가능)
• 그래프는 네트워크 모델이다.

 

트리(Tree)란 무엇인가?

트리

트리는 그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료구조이다.

그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조로 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 

이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다. 부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.

 

트리의 특징

• 부모-자식 관계가 존재해 레벨이 존재한다. (최상위 노드=Root)
• 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k (완전 이진트리의 경우)
• 방향성이 존재하고 사이클은 존재하지 않는다. (비순환)
• 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다.

 

트리와 그래프 비교

 

출처

[자료구조] 그래프와 트리(Graph, Tree)