그래프 기본 단위 : 정점과 간선으로 이루어진 집합 Gragh
1. 정점(vertex)은 분할 할수 없는 객체(점으로 표현되는 위치, 사람, 또는 물건등이 될수 있음 , 약자로 V or U
2. 간선(Edge) 은 정점을 잇는 선 (관계 또는 경로)
Indegree and outdegree
정점에서 나가는 간선 : Outdegree
정점으로 들어오는 간선 : Indegree
가중치
정점과 정점사이에 드는 비용
(e.g. 우리집(V)에서 판교(U)까지 가는데 드는 택시비용-> V에서 U까지 가는 가중치(=택시비용))
트리(Tree)는 계층적 구조를 가지며, 사이클이 없는 무방향 그래프
트리는 여러 가지 중요한 특성을 가지는데, 특히 노드 수와 간선 수 사이의 관계가 중요한 핵심
트리에서 노드의 수를 V (정점 또는 노드 수), 간선의 수를 E라고 할 때, 항상 다음 관계가 성립합니다:
E=V−1E = V - 1
트리 구조 예시:
1
/ \
2 3
/ \
4 5
/ \
6 7
E=V−1=7−1=6E = V - 1 = 7 - 1 = 6
따라서 이 트리는 간선 수가 V−1V - 1이라는 관계를 만족
루트 노드 : 가장 위에 있는 노드// 트리 탐색시 루트노드를 중심으로 탐색하면 문제가 쉽게 풀림
내부 노드 : 루트 및 리프노드 사이노드
리프노드 : 자식노드가 없는 노드
깊이 : 루트에서 해당 노드까지의 최단거리 (e.g. 5번 노드의 깊이는 2)
높이 : 루트노드에서 리프노드까지의 거리중 가장 긴 거리 (e.g. : 위의 트리는 높이가 3)
레벨 : 트리의 레벨은 문제마다 조금씩 다르지만 보통 깊이와 같은 의미
1번 노드가 0레벨이라면 2번노드는 1레벨// 민약 1번노드를 1레벨이라고 하면 2번노드는 2레벨
서브 트리 : 트리 내의 하위 집합// 트리내에 있는 부분집합
이진 탐색 트리 (Binary Search Tree) && 그래프*Graph (0) | 2024.12.16 |
---|---|
이진 트리 (Binary Tree) (0) | 2024.12.16 |
vector 벡터02 반복자(iterator) (2) | 2024.12.14 |
vector 벡터 (0) | 2024.12.14 |
자료구조 별 Big O 시간 복잡도 (0) | 2024.12.13 |