[자료구조] 트리와 그래프, 지하철 노선도에서 가계도까지 이해하는 자료구조 차이 - 코드카인 티스토리

안녕하세요 😊 코드카인 여러분!

오늘은 프로그래밍에서 자주 등장하는 **트리(Tree)**와 **그래프(Graph)**에 대해 알아볼 거예요. 둘 다 자료구조의 대표 주자인데요, 비슷해 보이지만 중요한 차이점이 있답니다. 트리와 그래프의 관계를 일상생활에 빗대어 쉽게 설명해드릴게요. 함께 시작해볼까요? 😊

---

🌳 트리(Tree)란?

트리는 마치 가계도나 회사 조직도 같은 모습이에요. 모든 구성원이 하나의 **최상위 노드(root)**를 중심으로 부모-자식 관계를 이루고 있죠.

주요 특징

1. 계층적 구조: 부모와 자식 관계가 명확합니다. 예를 들어, 부모 없이 혼자 있는 자식은 존재할 수 없어요.
2. 사이클 없음: 트리에서는 시작점에서 출발해 같은 노드로 다시 돌아올 수 없습니다.
3. 유일한 경로: 두 노드 간 이동 가능한 경로는 하나뿐입니다.

예시

       A
      / \
     B   C
    / \
   D   E

• A는 루트 노드, B와 C는 A의 자식, D와 E는 B의 자식이에요.
• 부모-자식 관계가 선명하죠?

---

🌐 그래프(Graph)란?

그래프는 우리가 살고 있는 도시 지하철 노선도 같은 거예요. 노드(정점)와 노드를 연결하는 선(간선)으로 이루어져 있는데, 누가 부모고 누가 자식인지 구분할 필요가 없어요.

주요 특징

1. 노드와 간선의 연결: 트리와 다르게 NODE 간 관계가 자유롭습니다.
2. 사이클 존재 가능: 어떤 경로로든 출발점으로 되돌아오는 게 가능합니다.
3. 방향성 여부: 간선에 방향이 있을 수도 없을 수도 있습니다.
   • 방향 그래프: 한쪽으로만 갈 수 있음 (예: 일방통행 도로)
   • 무방향 그래프: 양쪽으로 갈 수 있음 (예: 일반 도로)

예시

   A -- B
   |  / |
   C -- D

• A에서 출발해 C를 거쳐 다시 A로 돌아올 수 있어요(사이클).
• 연결의 제약이 없죠?

---

🌟 트리 vs 그래프: 차이점 총정리

특징트리(Tree)그래프(Graph)

구조	계층적 구조 (부모-자식 관계)	네트워크 구조 (자유로운 연결)
시작점	루트 노드 하나	시작점 없이 자유롭게 구성 가능
사이클	사이클 없음	사이클 존재 가능
경로 수	노드 간 유일한 경로	여러 경로 존재 가능
방향성	방향성이 내재되어 있음 (부모→자식)	방향 그래프 또는 무방향 그래프 존재 가능

---

🎯 트리와 그래프는 어디에 사용되나요?

트리(Tree)

• 파일 시스템: 폴더 안에 폴더가 또 들어가는 구조.
• 이진 검색 트리: 검색 효율을 높이기 위해 사용됨.

그래프(Graph)

• 소셜 네트워크: 친구 추천 알고리즘.
• 지도 앱: 최단 경로 찾기.

---

🛠️ 간단한 예제 코드

트리 구현 (Python)

class Node:
    def __init__(self, value):
        self.value = value
        self.children = []

root = Node('A')
child1 = Node('B')
child2 = Node('C')
root.children.extend([child1, child2])

그래프 구현 (Python)

from collections import defaultdict

graph = defaultdict(list)
graph['A'].extend(['B', 'C'])
graph['B'].extend(['A', 'D'])
graph['C'].append('A')
graph['D'].append('B')

---

😊 마무리하며..

트리와 그래프는 일상생활 곳곳에서 그 형태를 찾을 수 있어요. 자료구조의 기초를 탄탄히 하면 더 복잡한 문제도 쉽게 해결할 수 있답니다. 차근차근 학습하며 성장하는 여러분을 응원합니다! 화이팅! 😊