00. 트리와 그래프
- 알고리즘 문제를 풀다보니 문제 조건에서 그래프와 트리를 혼용 해 사용하는 경우가 많다고 느꼈다.
이에 정리가 한 번 필요하다고 느껴서 글을 작성하기로 했다. - 기본적으로 트리(Tree)는 그래프(Graph)에 속하는 하위 개념이다.
- 트리와 그래프의 차이점을 아래에서 차근차근 살펴보자.
01. 그래프 (Graph)
- 노드(하나의 점)과 노드를 연결하는 간선으로 구성된 자료구조.
-
순환 or 비순환 구조를 이룬다.
-
방향 그래프, 무방향 그래프가 있다.
-
'루트 노드' / '부모 - 자식 관계'라는 개념이 없다.
-
2개 이상의 경로가 가능하다. (무방향 / 방향 / 양방향)
-
네트워크 모델이다.
-
그래프에 대해서는 아래 글에서 한 번 다루었으니 참고해주시면 좋겠다.
https://velog.io/@takealittletime/자료구조-그래프Graph의-종류와-용어-표현방식
02. 트리 (Tree)
-
두 개의 노드 사이에 반드시 1개의 경로만을 가지며, 사이클이 존재하지 않는 방향 그래프
-
계층형 모델: 부모-자식 관계 성립, 레벨 존재 (최상위 노드 = Root)
-
노드 N개 → 간선은 N-1개
각 레벨 k에 존재하는 노드는 2^k개 (완전 이진 트리의 경우 가정) -
방향성 존재, 사이클은 존재 X (비순환)
-
전위순회, 중위순회, 후위순회 3가지 순회가 존재.
03. 그래프 (Graph) ↔ 트리 (Tree) 비교
| 구 분 | 그래프 (Graph) | 트리 (Tree) |
|---|---|---|
| 방향성 | 방향 / 무방향 | 방향만 |
| 사이클 | 순환 / 비순환 /자기순환 | 비순환만 |
| 루트노드 | 루트 개념 없음 | 한 개의 루트 존재 |
| 부모-자식 관계 (계층구조) | 부모-자식 관계 없음 | 1개의 부모 노드 (루트 제외) |
| 모델 | 네트워크 모델 | 계층 모델 |
| 간선 수 | 자유 | N-1개 |
참고 자료 / 이미지 출처 ::
-
[자료구조] 그래프와 트리(Graph, Tree)
https://bigsong.tistory.com/33 -
그래프 VS 트리 / 실생활 예시
https://hyojin96.tistory.com/entry/%EA%B7%B8%EB%9E%98%ED%94%84%EC%99%80-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%B0%A8%EC%9D%B4%EC%A0%90
능동적으로 사고하고, 성장하기 위한. 🌱