자료구조를 공부하다 보면 "트리(Tree)도 노드와 간선으로 되어 있고, 그래프(Graph)도 노드와 간선으로 되어 있는데 도대체 둘은 뭐가 다른 거야?"라는 의문이 생깁니다. 결론부터 말씀드리면 "트리는 그래프의 특수한 형태(부분 집합)이다"라고 정의할 수 있습니다. 즉, 모든 트리는 그래프이지만, 모든 그래프가 트리는 아닙니다.
하지만 실무나 면접에서는 이 둘을 엄격하게 구분해야 할 때가 많습니다. 데이터 모델링을 할 때 순환 참조를 허용할 것인지, 부모-자식 관계를 강제할 것인지에 따라 선택이 달라지기 때문입니다. 오늘은 트리와 그래프를 구분 짓는 결정적인 차이점 3가지를 명확하게 비교해 드리겠습니다.
1. 첫 번째 차이: 순환(Cycle)의 유무
트리와 그래프를 가르는 가장 큰 기준은 바로 '돌고 도는 길'이 있느냐입니다.
- 그래프: 순환(Cycle)이 존재할 수 있습니다. A에서 출발해서 B, C를 거쳐 다시 A로 돌아오는 경로가 허용됩니다. 지하철 2호선처럼 순환선이 있는 구조는 그래프로만 표현 가능합니다.
- 트리: 순환이 절대 존재할 수 없습니다 (Acyclic). 트리는 계층적 구조이기 때문에 밑으로 내려갔다가 다시 위로 올라와서 제자리로 돌아오는 것이 불가능합니다. 만약 트리에 선을 하나 더 그어서 순환이 생긴다면, 그 순간 그것은 트리가 아니라 그래프가 됩니다.
2. 두 번째 차이: 방향성과 계층 구조 (부모-자식)
두 자료구조가 바라보는 데이터의 '관계'가 다릅니다.
- 그래프: 평등한 관계입니다. 방향 그래프일 수도 있고 무방향 그래프일 수도 있습니다. 정점들 사이에 부모나 자식 같은 상하 위계질서가 없습니다. 친구 관계나 도로망처럼 서로 연결되어 있을 뿐입니다. 루트 노드(시작점)라는 개념도 딱히 없습니다.
- 트리: 철저한 계층(Hierarchy) 관계입니다. 반드시 방향성(위에서 아래로)을 가집니다. 부모 노드와 자식 노드라는 명확한 역할이 있으며, 모든 노드는 유일한 루트 노드(Root)로부터 뻗어 나옵니다.
3. 세 번째 차이: 루트 노드와 간선의 개수 규칙
구조적인 제약 조건에서도 큰 차이를 보입니다.
- 그래프: 루트 노드라는 개념이 없습니다. 어느 정점에서든 탐색을 시작할 수 있습니다. 또한, 간선의 개수에 제한이 없습니다. 모든 정점이 서로 다 연결되어 있어도 되고, 아예 연결이 끊긴(고립된) 부분이 있어도 그래프라고 부릅니다.
- 트리: 반드시 하나의 루트 노드가 존재해야 합니다. 그리고 간선의 개수에 엄격한 수학적 공식이 적용됩니다. 정점(노드)이 N개라면, 간선은 반드시 N-1개여야 합니다. 이보다 적으면 연결이 끊긴 것이고, 많으면 순환이 생깁니다.
4. 비교 요약표 (Comparison Table)
| 비교 항목 | 트리 (Tree) | 그래프 (Graph) |
|---|---|---|
| 상위 개념 | 그래프의 한 종류 (DAG의 일종) | 가장 포괄적인 네트워크 모델 |
| 순환 (Cycle) | 불가능 (Acyclic) | 가능 (Cyclic / Acyclic) |
| 루트 노드 | 1개 존재 | 없음 (모든 노드가 평등) |
| 부모-자식 | 존재함 (계층형) | 없음 (네트워크형) |
[핵심 요약]
1. 트리는 순환이 없고 계층 구조를 가지는 특수한 형태의 그래프입니다.
2. 트리는 루트 노드가 하나여야 하며, 노드가 N개일 때 간선은 정확히 N-1개입니다.
3. 모델링하려는 데이터가 순환(Loop)하거나 다대다(N:M) 관계라면 반드시 그래프를 사용해야 합니다.
1. 트리는 순환이 없고 계층 구조를 가지는 특수한 형태의 그래프입니다.
2. 트리는 루트 노드가 하나여야 하며, 노드가 N개일 때 간선은 정확히 N-1개입니다.
3. 모델링하려는 데이터가 순환(Loop)하거나 다대다(N:M) 관계라면 반드시 그래프를 사용해야 합니다.