1. 그래프(Graph)란?

1.1 그래프의 정의

• 그래프는 객체 간의 관계를 나타내는 추상적인 자료구조입니다.
• 그래프는 노드(또는 정점)와 간선으로 이루어져 있으며, 노드 간에 연결된 관계를 나타냅니다.

1.2 그래프의 구성 요소

• 노드(정점) : 객체를 나타내며 데이터를 저장합니다.
• 간선(에지) : 노드 사이의 관계를 나타내며, 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나뉩니다.
• 정점의 차수 : 노드에 연결된 간선의 수를 나타냅니다.
• 가중 그래프 : 간선에 가중치(가중값)가 할당된 그래프.

2. 트리(Tree)란?

2.1 트리의 정의

• 트리는 계층 구조를 가지는 비순환적인 그래프입니다.
• 트리는 하나의 루트 노드에서 시작하여 다양한 하위 노드로 확장되는 구조를 가집니다.

2.2 트리의 특징

• 단일 루트 : 모든 노드는 하나의 루트 노드로부터 시작합니다.
• 계층 구조 : 각 노드는 0개 이상의 하위 노드를 가집니다.
• 비순환성 : 트리는 순환 경로가 없는 구조입니다.

3. 그래프와 트리 비교

3.1 주요 차이점

• 그래프는 순환 구조일 수 있지만, 트리는 비순환 구조입니다.
• 그래프에는 루트 노드와 같은 특별한 노드가 없으며, 트리는 하나의 루트 노드를 가집니다.
• 그래프에서는 한 노드가 여러 다른 노드와 연결될 수 있지만, 트리에서는 노드는 부모와 자식 노드를 가집니다.

4. 활용 문제 풀어보기

그래프 문제

1. 무방향 그래프에 4개의 노드(A, B, C, D)와 다음과 같은 간선이 있습니다: (A-B), (B-C), (C-D), (D-A). 이 그래프의 노드와 간선 수는 각각 얼마인가요?
2. 방향 그래프에 3개의 노드(X, Y, Z)와 다음과 같은 간선이 있습니다: (X->Y), (Y->Z), (Z->X). 이 그래프의 노드와 간선 수는 각각 얼마인가요?

트리 문제

1. 루트 노드가 A이고, A에서 B, C, D로 갈 수 있는 트리가 있습니다. 이 트리의 높이(깊이)는 얼마인가요?
2. 이진 트리에서 각 노드는 최대 몇 개의 자식 노드를 가질 수 있을까요?