<aside> 💡 트리(Tree) 구조도 그래프 중 하나에 속합니다.
</aside>
| 정점 (Node, Vertex) | 데이터가 저장되는 위치의 개념 |
|---|---|
| 간선 (Edge, Branch) | 정점 간의 관계로 정점을 연결하는 선 |
| 인접 정점 (Adjacent Vertex) | 간선으로 직접 연결 된 두 개의 정점 |
| 가중치 (Weight) | 간선에 크기가 있을 때 그 가중치 값 |
| 차수 (Degree) | 정점에 이어져 있는 간선의 개수 |
| 진출 차수 (out-degree) 정점으로 들어오는 간선의 개수 | |
| 진입 차수 (in-degree) 정점에서 나가는 간선의 개수 | |
| 경로 길이 (Path Length) | 경로 내에 구성되어 있는 간선의 수 |
| 단순 경로 (Simple Path) | 각 정점을 1번만 방문하는 경로 |
| 순환 (Cycle) | 최소한 두 개의 서로 다른 노드로 구성되며, 같은 정점에서 시작되고 끝나는 경로 |
| (ex. 1 → 1 = {1, 3, 5, 1}) |
| 그래프 | 트리 | |
|---|---|---|
| 정의 | 정점(Node)과 정점들을 연결하는 간선(Edge)들의 집합 | 그래프의 한 종류로 계층적 구조를 표현할 때 사용할 수 있는 자료구조 |
| 방향성 | 방향, 무방향 그래프 모두 가능 | 방향 그래프 |
| 순환 | 순환 (Cycle) 가능 | 순환 (Cycle) 불가능 |
| 루트 노드 | 루트 노드의 개념이 존재하지 않음 | 부모가 없는 최상위 노드인 루트 노드가 존재함 |
| 부모-자식 | 부모-자식 관계가 존재하지 않음 | 부모-자식 관계가 존재함 |
| 모델 | 네트워크 모델 | 계층 모델 |
| 간선의 수 | 그래프에 따라 간선의 수가 상이함 | 노드가 N개일 때, N-1의 간선을 가짐 |
| 예시 및 종류 | 인터넷 연결 네트워크, 도로 교통 시스템, 지도 등 | 이진 트리, 포화 이진 트리, 완전 이진 트리, 이진 힙 등 |