백준 16437 문제를 풀면서 그래프, 트리의 차이가 제대로 정리되어 있지 않다는 것을 알았다. 그래서 정리해보려고 한다.
그래프
- 2개 이상의 경로가 가능
- 노드들 사이에서 무방향/방향에서 양방향 경로를 가질 수 있다.
- 루트노드라는 개념이 없다.
- 부모-자식 관계라는 개념이 없다.
- 그래프의 순회는 DFS, BFS로 이루어진다.
- 그래프는 싸이클을 형성하거나 형성하지 않는다.
- 방향 그래프와 무방향 그래프로 나눠진다.
- 간선의 유무는 그래프에 따라 다르다.
트리
- 트리는 그래프의 특별한 케이스이고, "최소 연결 트리"라고도 한다.
- 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
- 한 개의 루트 노드만이 존재하며, 모든 자식노드는 한 개의 부모노드만을 가진다.
- 트리의 순회는 전위순회, 중위순회, 후위 순회로 이루어진다.
- 사이클이 없는 방향 그래프의 한 종류이다.
- 이진트리, 이진탐색트리, 힙 등이 있다.
- 간선의 개수는 항상 (정점의 개수-1)이다.