[시나공] 그래프·트리 구조 핵심 정리

1️⃣ 그래프(Graph)

✅ 정의

• 그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 구성된 자료구조로, 객체 간의 연결 관계를 표현

✅ 방향 그래프 vs 무방향 그래프

• n = 정점(Vertex)의 개수

🔹 방향 그래프의 최대 간선 수

• 공식 : n(n-1)

예시) 정점 4개일 때  
→ 4(4-1) = 12

---

🔹 무방향 그래프의 최대 간선 수

• 공식 : n(n-1) / 2

• 중복 연결을 1개로 보기 때문에 2로 나눔

예시) 정점 4개일 때  
→ 4(4-1)/2 = 6

🎯 포인트

• “최대 간선 수”는 공식 암기 문제로 자주 출제

---

2️⃣ 트리(Tree)

✅ 정의

• 트리는 정점(Node)과 간선(Branch)으로 구성
• 사이클(Cycle)이 존재하지 않는 그래프
• 계층적 구조 표현

---

✅ 특징

• 루트 노드 1개 존재

• 모든 노드는 유일한 부모를 가짐

• 노드 수가 n개일 때 간선 수는 n-1

• 공식 : 트리의 간선 수 = 노드 수 - 1

---

3️⃣ 트리 관련 용어

✅ 주요 용어 정리

구성 요소	의미
루트 노드 (Root Node)	트리의 최상위 노드
부모 노드 (Parent Node)	특정 노드의 바로 위에 연결된 노드
자식 노드 (Child Node)	특정 노드의 바로 아래에 연결된 노드
형제 노드 (Siblings)	같은 부모를 가진 노드들
간선 (Edge)	노드와 노드를 연결하는 선
내부 노드 (Internal Node)	자식이 하나 이상 존재하는 노드 (Leaf가 아닌 노드)
부분 트리 (Sub Tree)	트리 내의 특정 노드를 루트로 하여 그 노드의 모든 자손을 포함하는 트리
디그리 (Degree, 차수)	해당 노드에서 뻗어 나가는 자식의 수 트리의 디그리 = 노드들 중 최대 차수
단말 노드 (Terminal Node, Leaf Node)	자식이 없는 노드 (Degree = 0)
레벨 (Level)	루트를 Level 1로 가정하고 아래로 내려갈 때마다 +1
깊이 (Depth / Height)	트리에서 가질 수 있는 최대 레벨 수
숲 (Forest)	여러 개의 트리 집합

---

📊 시험 포인트 정리

🔥 1. 최대 간선 수 공식 문제

• 방향/무방향 구분 문제
• 정점 개수 제시 → 간선 수 계산

---

🔥 2. 트리 여부 판별 문제

• 사이클 존재 여부
• 간선 수 = n-1인지 확인
• 연결 그래프 여부 확인

---

🔥 3. 트리 용어 정의 문제

• 디그리
• 단말 노드 개수
• 트리의 깊이
• 숲 개념

---

📌 암기 핵심 요약

• 방향 그래프 최대 간선 = n(n-1)
• 무방향 그래프 최대 간선 = n(n-1)/2
• 트리 간선 수 = n-1
• 트리 = 사이클 없음
• 단말 노드 = Degree 0
• 트리 디그리 = 최대 차수

2025 시나공 퀵이지 정보처리기사 실기 단기완성
(저자: 강윤석, 김용갑, 김우경, 김종일 | 출판사: 길벗)

※ 본 글은 위 교재를 참고하여 학습 목적으로 재정리한 내용입니다.