[Data Structure] Graph 와 Tree 의 차이점

Graph(그래프)

 

  1.  정의

 

    -  노드(정점)와 노드(정점)간을 연결하는 간선으로 구성된 자료 구조

 

    -  연결되어 있는 객체간의 관계 표현 가능

 

    -  계층이 없는 네트워크 모델

 

  2.  특징

 

    -  노드 간에 2개 이상의 경로도 가능

 

    -  순환(사이클)/비순환 구조 가능

 

    -  방향성 있는 그래프와 방향성이 없는 그래프 모두 가능

 

Tree(트리)

 

  1.  정의

 

    -  그레프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조

 

    -  그래프의 한 종류

 

    -  루트 노드가 존재하고 -> 부모-자식 관계로 이루어진 계층적인 모델

 

  2.  특징

 

    -  방향성 O 

 

    -  사이클이 존재하지 않는 비순환 구조

 

    -  계층 모델로, 깊이와 높이라는 개념 존재

 

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

 

 

 

참고

 

  -  https://rays-space.tistory.com/22

 

  -  https://gusrb3164.github.io/computer-science/2021/04/16/graph,tree/