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

트리와 그래프

 

그래프(Graph)

<그래프>

그래프란

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

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

 

그래프의 특징

- 그래프는 순환 혹은 비순환 구조를 이룬다

- 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있다.

- 루트 노드의 개념이 없다 / 부모-자식 관계라는 개념이 없다.

- 2개 이상의 경로가 가능하다.(무방향, 방향, 양방향 가능)

- 그래프는 네트워크 모델이다.

 

 

트리(Tree)

트리란

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

그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조이다.

트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며

사이클이 존재하지 않는 방향 그래프이다.

이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다.

부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.

 

트리의 특징

- 부모-자식 관계가 존재해 레벨이 존재한다.(최상위 노드=Root)

- 노드가 N개이면 간선은 N-1개 / 각 레벨 k에 존재하는 노드는 2^k개(완전이진트리의 경우)

- 방향성이 존재하고 사이클은 존재하시 않는다.(비순환)

- 트리의 순회는 전위순회, 중위순회, 후위순회 3가지가 존재한다.

 

 

트리와 그래프 비교

	그래프	트리
방향성	방향, 무방향	방향만
사이클	순환, 비순환, 자기순환	비순환만
루트노드	루트 개념 없음	한 개의 루트 존재
부모-자식	부모-자식 개념없음	1개의 부모노드(루트 제외)
모델	네트워크 모델	계층 모델
간선 수	자유	N-1개