Tree and Graph

📘 Tree and Graph

Tree

트리는 그래프와 같이 노드와 노드간을 연결하는 간선으로 구성된 자료구조이다. 그러나 트리는 그래프 중에서도 특수한 케이스에 해당하는 자료구조이다. 트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다. 이러한 특성 때문에 ‘최소 연결 트리’라고 부르기도 한다. 부모-자식 관계가 성립하기 때문에 계층형 모델이라고도 한다.

Graph

그래프는 노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다.

차이점

  그래프 트리 방향성 방향, 무방향 방향만

사이클 순환, 비순환, 자기순환 비순환만

루트노드 루트 개념 없음 한 개의 루트 존재

부모-자식 부모-자식 개념없음 1개의 부모노드(루트 제외)

모델 네트워크 모델 계층 모델

간선 수 자유 N-1개

둘의 비교

단일 루트 노드가 있고 주기가 없다면 트리일 가능성이 높다. 주기가 있거나 연결이 끊어진 구성 요소가 여러 개 있는 경우 그래프일 가능성이 높다.

트리의 경우 순회(예: BFS 또는 DFS)를 수행하고 모든 노드가 정확히 한 번 방문하고 주기가 없는지 확인할 수 있다. 그래프의 경우 동일한 순회를 수행하고 순환 또는 연결이 끊긴 구성 요소를 확인할 수 있다. 이러한 특성을 조사함으로써 데이터 구조를 트리 또는 그래프로 정확하게 분류할 수 있다.