1030
1.그래프(Graph)란?
1.1 그래프의 정의
1.2 그래프의 구성 요소
2. 트리(Tree)란?
2.1 트리의 정의
2.2 트리의 특징
3. 그래프와 트리 비교
3.1 주요 차이점
4. 활용 문제 풀어보기
1. 트리(tree)
1.1. 정의
사이클을 허용하지 않는(동일한 경로로는 되돌아 갈 수 없다고 가정할 때, 한 노드에서 출발하여 원위치로 돌아올 수 없는) 구조
1.2. 구성 요소
-
노드(node) : 트리 구성의 기본 요소
- A, B, C ...
-
근 노드(root node) : 가장 상위 노드
- A
-
부모 노드(parent node) : 한 단계 상위 노드
- D와 E의 부모 노드는 B
-
자식 노드(child node) : 한 단계 하위 노드
- D의 자식 노드는 G와 H
-
형제 노드(silbling node) : 부모가 같은 노드
- G와 H는 같은 부모(D)를 가지고 있으므로 형제 노드이다.
-
차수(degree) : 자식 노드 수
- A의 차수는 3이다.
-
트리의 차수(degree) : 트리에서 가장 큰 차수
- 근 노드인 A의 차수가 3이므로, 위의 트리의 차수는 3이다.
-
단말 노드(terminal node) : 차수가 0인 노드
- E, G, H, I
-
레벨(level) : 근 노드를 1로 하여 자손으로 내려갈수록 1씩 증가한다.
- A의 레벨은 1, G의 레벨은 4
-
깊이(depth) : 트리의 최대 레벨
- 단말 노드인 G의 레벨이 4이므로, 깊이는 4이다.
-
서브 트리(sub tree) : 특정 노드를 제거했을 때 생기는 하위 트리
- B를 제거하면 root가 A인 트리, root가 D인 트리, root가 E인 트리, 총 3개가 생긴다.
1.3. 트리의 특징
트리는 그래프와는 달리 비선형구조이다.
비선형 구조는 트리구조와 같이 아래로만 뻗어 나가는 계층적 구조이다. 즉, 사이클이 존재할 수 없다.
2. 그래프 (Graph)
2.1. 정의
자료를 갖고 있는 정점(Vertex)과 정점을 연결하는 간선(Edge)으로 구성되는 자료구조
그래프는 전기회로 분석, 최단거리 탐색, 컴퓨터 네트워크, 인공지능 등에 활용됩니다.
2.2. 그래프 용어
-
인접(Adjacent) : 정점과 정점 사이에 연결선이 있고 직접 접근이 가능한 경우
-
경로(Path) : 출발에서 목표 지점까지 정점들의 순서
- 정점 사이는 무방향
ㅡ, 또는 방향->간선으로 표시한다.
- 정점 사이는 무방향
-
단순경로(Simple Path) : 경로 상의 모든 정점들이 다를 경우.
단, 출발과 목표 정점은 같을 수 있다. -
사이클(Cycle) : 출발과 목표 정점이 같은 단순 경로
- 출발과 도착 사이에 중복되는 정점들이 존재하면 사이클 성립이 되지 않는다.
-
차수(Degree) : 한 정점에 연결된 간선의 수
- 진입차수 : 들어오는 간선
- 진출차수 : 나가는 간선
무방향 그래프에서 진입차수와 진출차수는 동일하다
2.3. 그래프의 특징
- 루트 노드라는 개념이 없다.
- 부모-자식관계라는 개념이 없다.
- 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
- 간선의 유무는 그래프에 따라 다르다.
- 그래프는 순환 혹은 비순환이다.
3. 트리(Tree)와 그래프(Graph)의 비교
| 트리 | 그래프 | |
|---|---|---|
| 방향성 | 방향성이 있다 | 방향성이 있는 그래프와 없는 그래프가 있다 |
| 사이클 순환 | 불가능 | 가능 |
| 루트 노드 | 1개의 루트가 존재한다 | 루트라는 개념이 존재하지 않는다 |
| 계층 관계 | 루트를 제외하고 1개의 부모노드가 있다 | 부모-자식이라는 계층 개념이 존재하지 않는다 |
| 간선 수 | 정점의 개수-1개가 존재한다 | 자유롭다 |
| 모델 | 계층 모델 | 네트워크 모델 |
| 경로 | 1개의 경로만 가능하다 | 2개 이상의 경로도 가능하다 |
4. 트리(Tree) & 그래프(Graph) 활용 문제 풀어보기
Q1. 그래프는 트리인가?
Q2. 트리는 그래프인가?
- 위의 그림은 그래프이다
Q3. 위의 그림에서 정점 F의 인접은?
Q4. 위의 그림에서 단순경로가 되는 경로를 서술하시오. (단, 정점의 개수는 5개 이상이어야 함)
Q5. 위의 그림에 있는 그래프는 방향성이 있는가?
