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

Graph

• 그래프(Graph)

  • 노드와 노드간을 연결하는 간선으로 구성된 자료 구조
  • 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 구조

• 특징

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

Tree

• 트리(Tree)

  • 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 이루어진 자료 구조

• 특징

  • 그래프의 한 종류이다.
  • 방향성이 있으며 사이클이 존재하지 않는다. (비순환 그래프)
  • 부모 - 자식 관계라는 개념이 있으며 최상위에 Root노드가 존재한다.

트리와 그래프의 차이점

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