🧐 트리와 그래프를 개별적으로 공부했지만서도 연관 관계를 좀 정리해두고 싶다.
Graph
- 2개 이상의 경로가 가능하다.
- 무방향에서 양방향으로도 가능하다.
- 루트 노드 개념이 없고, 부모-자식 개념도 없다.
- 그래프 순회는 BFS, DFS로 이루어져 있다.
- 그래프는 네트워크 모델이다.
Tree
- 트리는 그래프의 특별한 케이스
- "최소 연결 트리"라고도 불린다.
- 루트 노드 개념이 있고, 부모-자식 개념도 있다.
- 자기 자신을 돌 수 없고 loop 순환 역시 불가하다.
- 부모-자식 관계 흐름은 상하이다.
- 트리의 순회는 전위, 중위, 후위 순회로 이어지고, 이들은 모두 그래프의 DFS, BFS 안에 있다.
- 트리에는 이진트리, 이진탐색트리, 힙트리, AVL트리 등이 있다.
- 트리는 계층 모델이다.
DFS는 이진트리의 전위, 중위, 후위 탐색에 사용된다.
아주 간단하게 위의 전위 순회 예시만 보더라도 DFS라는 것을 알 수 있다.
Reference
developer