그래프와 트리의 차이점

그래프

 

1) 2개 이상의 경로가 가능하다. 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.

2) self-loop 뿐 아니라 loop/circuit 모두 가능하다.

3) 루트 노드라는 개념이 없다

4) 부모-자식 관계라는 개념이 없다

5) 그래프의 순회는 DFS나 BFS로 이루어진다.

6) 그래프는 Cyclic 혹은 Acyclic이다.

7) 그래프는 크게 방향 그래프와 무방향 그래프가 있다.

8) 간선의 유무는 그래프에 따라 다르다.

9) 그래프는 네트워크 모델이다

 

 

트리

 

1) 트리는 그래프의 특별한 케이스이며 "최소 연결 트리"라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다.

2) loop나 circuit이 없다. 당연히 self-loop도 없다.

3) 한 개의 루트 노드만이 존재하며 모든 자식노드는 한 개의 부모노드만을 가진다.

4) 부모-자식 관계이므로 흐름은 top-bottom 아니면 bottom-top으로 이루어진다.

5) 트리의 순회는 Pre-order, In-order 아니면 Post-order로 이루어진다. 이 3가지 모두 DFS/BFS안에 있다.

6) 트리는 DAG(Directed Acyclic Graphs)의 한 종류이다. DAG는 사이클이 없는 방향 그래프를 말한다.

7) 트리는 이진트리, 이진탐색트리, AVL 트리, 힙이 있다.

8) 간선은 항상 정점의개수-1 만큼을 가진다.

9) 트리는 계층 모델이다.

 

 

가장 큰 차이점은 그래프는 순환이 가능하다는 점이다.

 

그래프에서의 노드와 노드는 모두 동등 관계지만

트리에서는 부모노드와 자식노드가 존재하기 때문에 모든 노드가 동등한 입장이 아니다.

또한 그래프는 가중치 및 방향성을 가질 수 있다.