그래프 vs 트리

그래프를 탐색하는 두 알고리즘으로 DFS/BFS에 대해서 공부하고 있다.

 

그래프를 탐색하는 알고리즘에 대해서 공부하고 있으면서 나는 그래프가 무엇인지도 모르고 있었다.

 

그래프가 '여러개의 노드와 이들을 연결하는 간선으로 이루어진 자료구조'인 것은 지난 포스팅을 통해 알게되었는데,

 

그래프의 그림을 보니 트리와의 차이점을 모르겠다는 생각이 들었다.

 

이번 포스팅에서는 '그래프'와 '트리'의 차이점에 대해서 알아보도록 하자.

 

TREE & GRAPH

 

그래프(Graph)?

• 여러개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조
• 즉, 연결된 객체 간의 관계를 표현할 수 있는 자료구조

 

그래프의 특징

• 그래프는 네트워크 모델이다.
• 그래프는 순환 혹은 비순환 구조를 이룬다.
• 그래프는 루트노드라는 개념이 없다. 부모 - 자식 관계 개념 역시 없다.
• 그래프는 방향성이 있는 그래프와 방향성이 없는 그래프가 있다.
• 노드간에 2개 이상의 경로도 가능하다.

 

트리(Tree)?

• 그래프와 같이 여러개의 노드(node)와 이들을 연결하는 간선(edge)으로 이루어진 자료구조
• 그러나, 트리는 그래프 중에서도 특수한 캐이스에 해당하는 자료구조이다
• 트리는 두 노드 사이에 반드시 한 개의 경로만을 가진다.
• 사이클이 존재하지 않는 방향 그래프이다.

 

트리의 특징

• 그래프의 한 종류이다.
• 부모 - 자식 관계가 존재해 레벨이 존재한다. (최상위 노드=Root)
• 방향성이 존재하고 사이클이 존재하지 않는다.(비순환 그래프)
• 그래프는 루트노드라는 개념이 없다. 부모 - 자식 관계 개념 역시 없다.

트리와 그래프의 차이점 정리

	그래프	트리
정의	노드와 그 노드를 연결하는 간선으로 구성된 자료구조	그래프의 한 종류, 방향성이 있는 비순환 그래프
방향성	방향, 무방향 모두 존재	방향 그래프만 존재
사이클	순환, 비순환, 자기순환	비순환만 존재
루트노드	루트 노드 개념 없음	한 개의 루트 존재
부모-자식	부모-자식 개념없음	1개의 부모노드
모델	네트워크 모델	계층 모델
간선 수	자유	N - 1 개
순회	DFS, BFS	DFS, BFS 방식의 전위, 중위, 후위
경로		임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단경로, 선수과목, 후수과목	이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙