[CS 자료구조] 그래프와 트리의 차이

그래프(Graph)

• 다양한 종류의 물리적 구조를 나타낼 수있는 수학적 비선형 데이터 구조
• 그래프의 정점(vertex,node)은 점 또는 원으로 표시되고 모서리는 호 또는 선 세그먼트로 표시
• 정점의 집합이 V, 변의 집합이 E인 그래를 G=(V,E)라고 표현
• 두점 u,v를 연결한 변 Edge는 E (u, v)로 표시

 

종류

• 무향 그래프와 ,유향그래프로 나뉘어 짐
• 변 에는 다양한 속성이 있음 대표적으로 비용(cost)가 존재

 

 

 

특징

• 인접한 정점 - 정점 a는 정점 b에 인접합니다 (a, b) 또는 (b, a).
• 경로 - 임의의 정점 w의 경로는 인접한 정점 시퀀스입니다.
• 사이클 - 첫 번째와 마지막 버텍스가 동일한 경로입니다.
• Degree - 정점에 입사하는 다수의 가장자리입니다.
• 연결된 그래프 - 임의의 정점에서 다른 정점까지의 경로가있는 경우 해당 그래프를 연결된 그래프라고합니다.
• 폐로 - 시작점과 종점이 같은 경로(즉 사이클이 존재)

 

트리(Tree)

• 폐로를 가지지 않는 연결 그래프를 트리라 함(즉 사이클이 존재 X)
• 트리의 간선의 수 =  노드수 -1 
• 트리는 정렬 된 순서로 데이터 항목을 정렬하는 비선형 데이터 구조

 

종류

• 이진 트리, 이진 탐색 트리, AVL 트리, 스레드 이진 트리, B- 트리 등의 여러 가지 유형의 트리가 존재

 

특징

• Edge - 두 노드를 연결하는 선.
• 레벨 - 루트 노드가 레벨 0에있는 것과 같은 방식으로 트리가 레벨 로 분할됩니다. 그 직계 하위 노드는 레벨 1에 있고 그 직계 하위 노드는 레벨 2에 있고 터미널 노드 또는 리프 노드까지 있습니다.
• Degree - 주어진 트리에서 노드의 하위 트리 수입니다.
• Depth - 주어진 트리에서 노드의 최대 레벨이며 높이 라고도합니다.
• 터미널 노드 - 최상위 노드는 터미널 노드이며 터미널 및 루트 노드를 제외한 다른 노드는 비 터미널 노드로 알려져 있습니다.

트리

 

 

트리와 그래프 차이

	Tree	Graph
경로	두 꼭지점 사이에 하나만 존재	둘 이상의 경로가 허용
루트노드	하나의 루트노드 존재	루트 노드 존재x
사이클	사이클이 존재x(폐로가 존재x)	사이클을 가질수 있음
복잡성	덜복잡	트리보단 복잡
탐색 기법	전위, 중위 ,후위 ,DFS, BFS	DFS,BFS
간선의 수	N개의노드일때 N-1의 간선을 가짐	0개이상