그래프와 트리의 차이점에 대해서 설명해 주세요.

[duyeonnn]

그래프와 트리의 차이점에 대해서 설명해 주세요.

[sustainable-git]

	Graph	Tree
정의	node와 node를 연결하는 간선으로 구성된 자료구조	방향성이 있는 비순환 Graph
방향성	방향, 무방향	방향
cycle	순환, 비순환	비순환
root	-	한 개의 root node
parent child	-	root를 제외하고 하나의 부모를 가짐
model	network	계층
간선의 수	-	N개의 node는 N-1개의 간선
경로	-	임의의 두 Node간 경로는 유일

[inuinseoul]

트리는 노드와 브랜치를 이용해 사이클이 이루어지지않게 구성되어 있습니다. 가장 정점이 되는 root node가 존재하며 계층적으로 구성되어 있다는 것이 특징입니다. 그래프도 마찬가지로 노드로 구성되어 있지만 사이클이 생겨도 상관없다는 점이 다릅니다. 또한 계층과 상관없이 자유롭게 구성되어 있습니다.

[duyeonnn]

그래프

• 2개 이상의 경로가 가능하고 노드들 사이에 무방향/방향 에서 양뱡향 경로를 가질 수 있다
• self-loop 뿐 아니라 loop/circuit 모두 가능하다
• 루트 노드라는 개념이 없다
• 부모-자식 개념이 없다
• 그래프 순회는 DFS나 BFS로 이루어진다
• 그래프는 Cyclic 혹은 Acyclic이다
• 간선의 유무는 그래프에 따라 다르다
• 그래프는 네트워크 모델이다

트리

• 트리는 그래프의 특별한 케이스이며 최소 연결 트리라고도 불린다. 두개 정점 사이에 반드시 1개의 경로만을 가진다
• loop나 circuit이 없고 self-loop도 없다
• 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모 노드만을 가진다
• 부모-자식 관계이다
• 트리의 순회는 Pre-order, In-order, Post-order가 있다
• 트리는 DAG(사이클이 없는 방향 그래프)의 한 종류이다.
• 이진트리, 이진탐색트리, AVL트리, 힙 등이 있다.
• 간선은 항상 정점의 개수-1 만큼을 가진다
• 트리는 계층 모델이다