트리와 그래프
(그래프 ⊃ 트리 로도 볼 수 있음)
- 공통점
노드와 노드 간을 연결하는 간선으로 구성된 자료구조
- 차이점
| 트리 | 그래프 | |
| 모델 | 계층 모델 | 네트워크 모델 |
| 방향 | 방향 | 무방향, 방향, 양방향 |
| 순환 | 비순환 | 순환, 비순환, 자기순환 |
| 간선 수 | 노드 수 - 1 | 자유 |
| 기타 | 루트 노드, 부모-자식 노드 개념 有 |
트리
- 구성 요소 및 용어
Node (노드) : 트리를 구성하는 각각의 요소
Edge (간선) : 노드와 노드를 연결하는 선
Root Node (루트 노드) : 트리 구조 최상위에 있는 노드
Parent Node (부모 노드) : 자식 노드를 가진 노드
Chlid Node (자식 노드) : 부모 노드를 가진 노드
Sibling Node (형제 노드) : 같은 부모를 가지는 노드
Terminal Node (단말 노드) : 자식 노드가 없는 노드 (=Leaf Node, External Node, Outer Node)
Internal Node (비단말 노드) : 자식 노드가 있는 노드 (=Branch Node, Internal Node, Inner Node)
Depth (깊이) : 어떤 노드에서 루트 노드까지 가장 긴 경로의 간선 수
Height (높이) : 어떤 노드에서 단말 노드까지 가장 긴 경로의 간선 수
Level : 루트 노드로부터 임의의 노드까지의 깊이 (루트 노드의 레벨 = 1)
Degree : 노드의 자식 수 (=서브 트리의 수)
Path : 한 노드에서 다른 한 노드 사이에 놓인 노드들 순서
Path Length : 해당 경로에 있는 총 노드 수
Size : 자신을 포함한 자손의 노드 수
Width : 해당 레벨에 있는 노드 수
Breadth : 리프 노드의 수
Distance : 두 노드 사이 최단 경로에 있는 간선 수
Order : 부모 노드가 가질 수 있는 최대 자식 수 (이진 트리는 order = 2)
- 특징
방향성 존재하는 비순환 연결 그래프
트리 내에 또 다른 트리(서브 트리)가 있는 재귀적 자료구조
일반적으로 삽입, 삭제 수행 시 O(logN)의 낮은 시간복잡도 가짐
- 순회 (노드, 간선 탐색)
1. 전위 레벨 순회 (Pre-order Traversal) (=DFS) : 루트 노드 → 자식 노드 탐색
2. 중위 레벨 순회 (In-order Traversal) (=DFS) : 왼쪽 자식 노드 → 루트 노드 → 오른쪽 자식 노드 탐색
3. 후위 레벨 순회 (Post-order Traversal) (=DFS) : 왼쪽 자식 노드 → 오른쪽 자식 노드 → 루트 노드 탐색
4. 레벨 순회 (Level-order Traversal) (=BFS) : 루트 노드 → 다음 레벨 노드 탐색
- 구현 방법
1. 배열
장점 : 노드에 접근하는 속도 빠름, 구현 편리
단점 : 편향 트리의 경우 메모리 낭비 발생, 배열 크기 이상의 노드 추가 불가
2. 인접 리스트
public class Node {
int value;
Node left;
Node right;
}
장점 : 삽입, 삭제 편리, 노드 수에 제한 X (포인터로 연결됨)
단점 : 접근 속도 느림
- 종류
이진 트리, 이진 탐색 트리
=> 하위 카테고리가 많아 각 종류마다 게시글 작성하여 설명할 예정
(이진 트리 유형 : https://frombasics.tistory.com/266)
그래프
- 구성 요소 및 용어
Vertex (정점) : 데이터가 저장되는 객체 (=Node)
Edge (간선) : 정점을 연결하는 선 (=Link, Branch)
Adjacent Vertex (인접 정점) : 간선에 의해 직접 연결된 정점
Simple Path (단순 경로) : 경로 중에서 반복되는 정점이 없는 경우
Degree (차수) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
In-degree (진출 차수) : 방향 그래프에서 외부로 향하는 간선의 수
Out-degree (진입 차수) : 방향 그래프에서 외부에서 들어오는 간선의 수
Path Length (경로 길이) : 경로를 구성하는데 사용된 간선의 수
Cycle (사이클) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
1. DFS (Depth First Search)
2. BFS (Breadth First Search)
- 구현 방법
1. 인접 행렬
그래프의 노드를 2차원 배열로 표현 (노드 간에 직접 연결되면 1, 아니면 0 삽입)
장점 :
두 정점에 대한 간선 조회 시 O(1)라는 낮은 시간복잡도 가짐
차수 구할 시 인접 행렬 내 특정 행 값을 더하면 되므로 O(n)의 시간복잡도 가짐
인접리스트에 비해 구현 편리
단점 :
모든 간선 파악해야 할 시 O(n^2)라는 높은 시간복잡도 가짐
2차원 배열로 인한 메모리 공간 낭비
2. 인접 리스트
그래프의 노드를 리스트로 표현 (노드 간에 직접 연결 시 노드의 인덱스에 해당 노드(리스트) 삽입)
장점 :
정점들의 연결 정보 탐색 시 O(n)의 시간복잡도 가짐
필요한 만큼의 메모리 공간만 사용
단점 :
특정한 두 정점 간선 조회 시 인접 행렬에 비해 시간 오래 소요됨 (O(E), E= 간선 개수)
구현이 비교적 복잡함
- 종류
1. 무방향 그래프 : 간선에 방향이 없는 그래프
2. 방향 그래프 : 간성에 방향성이 존재해 지정된 방향대로만 이동 가능한 그래프
3. 완전 그래프 : 모든 정점들이 서로 연결되어 최대 간선 수를 갖는 그래프
4. 부분 그래프 : 기존 그래프에서 일부 정점 ,간선 제외해 생성한 그래프
5. 가중치(네트워크) 그래프 : 간선에 가중치 할당한 그래프
6. 연결 그래프 : 무방향 그래프에서 모든 정점에 대해 간선 존재하는 그래프
7. 비연결(단절) 그래프 : 무방향 그래프에서 특정 정점에 대한 간선이 존재하지 않는 그래프
8. 순환(사이클) 그래프 : 단순 경로에서 시작 정점과 종료 정점이 동일한 그래프
9. 비순환 그래프 : 사이클이 존재하지 않는 그래프 (시작 정점, 종료 정점 다름)
출처 :
'Programming > 알고리즘' 카테고리의 다른 글
| [자료구조] 이진 탐색 트리 (0) | 2023.06.02 |
|---|---|
| [자료구조] 트리 - 이진 트리 유형 (0) | 2023.05.24 |
| DFS, BFS (0) | 2023.05.04 |
| DP(Dynamic Programming, 동적 계획법) (0) | 2023.04.07 |
| [자료구조] 선형 구조 - 스택(Stack), 큐(Queue), 덱(Deque) (0) | 2023.03.20 |
