Related to: Data Structures
개요
Graph와 Tree는 비선형 자료구조의 대표적인 두 형태입니다. 트리는 그래프의 특수한 형태(사이클이 없는 연결 그래프)입니다.
핵심 개념
Graph
그래프는 vertex와 edge로 구성된 비선형 자료구조이다. vertex는 정점, edge는 정점과 정점을 연결하는 간선이다. 최상위 노드(Root Node)가 존재하지 않는다. 여러 개의 edge를 가질 수 있다.
Tree
트리는 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다. 최상위 노드가 존재한다. 부모로 노트로 연결하는 edge와 자식 노트로 연결하는 edge를 가질 수 있다.
그래프 vs 트리 비교
| 구분 | 그래프(Graph) | 트리(Tree) |
|---|---|---|
| 루트 노드 | 없음 | 있음 |
| 사이클 | 가능 | 없음 |
| 방향성 | 방향/무방향 모두 가능 | 부모→자식 방향 |
| 간선 수 | 제한 없음 | 노드 수 - 1 |
관련 개념
- Graph — 그래프 자료구조 상세 노트
- Tree — 트리 자료구조 상세 노트
- Binary Tree란 무엇일까 — 이진 트리의 종류와 특성
- Heap — 완전 이진트리 기반 자료구조
- Data Structure — 자료구조 개요
- Depth-First Search(DFS, 깊이 우선 탐색) — 그래프/트리 탐색 알고리즘
참조
https://ko.wikipedia.org/wiki/그래프_(자료_구조))