그래프와 트리의 차이는?

[ 그래프 (Graph) ]

 

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

[ 트리 (tree) ] 

 

• 트리는 그래프의 특별한 케이스이며, "최소 연결 트리" 라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.
• Loop 나 Circuit이 없다. 당연히 Self-Loop 도 없다
• 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만을 가진다.
• 부모-자식 관계이므로 흐름은 Top-down 아니면, Bottom-up으로 이루어진다.
• 트리의 순회는 Pre-order, In-order 아니면, Post-order로 이루어진다. 이 3가지 모두 DFS / BFS 안에 있다.
• 트리는 DAG(Directed Acyclic Graphs)의 한 종류이다. DAG는 사이클이 없는 방향 그래프를 말한다.
• 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.
• 간선은 항상 정점의 개수-1 만큼을 가진다.
• 트리는 계층 모델이다.

 

출처

http://freefeast.info/difference-between/difference-between-trees-and-graphs-trees-vs-graphs/

Difference between Trees and Graphs | Trees vs. Graphs - FreeFeast.info : Interview Questions ,Awesome Gadgets,Personality Motiv