비선형 자료구조
1. 트리
트리란 계층적인 관계를 나타내는 노드의 집합체
트리의 특징
1) 모든 노드는 0개 혹은 그 이상의 자식노드를 가진다.
2) 루트 노드를 제외한 각 노드는 하나의 부모노드를 가진다.
degree: 한 노드가 가지는 자식의 수
-> leaf(degree가 0) / internal(degree가 1 이상)
sibling: 같은 부모노드를 가지는 노드
트리자녀의 순서 여부에 따라 ordered tree / unordered tree
-> 대부분 unoredered tree이나 가계도와 같은 특수한 경우에는 ordered tree 일 수 있음
path(경로): 트리에서 노드의 sequence
-> 바로 앞 노드가 다음 노드의 부모여야 함
-> 경로의 길이: 경로의 노드를 잇는 선의 개수
depth(깊이): 루트노드로부터 해당 노드까지의 길이
-> 루트노드로부터 선택된 노드까지의 경로는 unique하다.
height(높이): 모든 노드의 depth 중 가장 큰 값
ex.루트노드만 있다면 0 / 노드가 없는 경우(도 트리일 수 있음) -1
ancestor, descendant: ancestor가 descendant보다 항상 위에 존재
-> 일반적으로 자기 자신은 자기 자신의 조상이자 자손이다.
-> strict 경우에는 자기 자신을 제외한다.
자식노드들의 list representation을 주로 사용
-> A노드는 3개의 자녀를 가지고 있기 때문에 3개의 포인터
-> 각각의 포인터는 A노드의 자식인 B, C, D를 참조
2. 그래프
그레프? 데이터 사이의 인접한 관계
object(vertex): 저장하고자 하는 객체
edge(arc,link): 관계성
undirected graph: 방향이 없는 그래프
-> N개의 vertex? v1부터 vN까지의 N개의 vertex
-> edge ? {Vi, Vj}로 표현 (Vi->Vj, Vj->Vi)
V개의 vertex가 있는 undirected 그래프에서 edge의 최대 개수?
V * (V - 1) / 2
degree: 자기자신의 adjacent한 이웃의 개수
sub graph: vertex와 엣지를 샘플링해서 일부만 가져 왔을 때
-> 모든 vertex와 edge가 original graph에 존재해야 한다.
path(경로): (V1, ..., Vk)로 표현, 인접한 vertex는 반드시 엣지 존재
-> 경로의 길이: 경로의 vertex를 잇는 엣지의 개수(undirected 그래프)
-> trivial path: length가 0인 것(자기자신에 머물러있는 것)
simple path: 경로상에 처음과 마지막을 제외했을 때, 안에서 중복이 없는 경로
simple cycle: simple path이면서 처음과 마지막 vertex 같은 것
connected?
connected vertex : 두 vertex 사이에 경로가 있는 것
connected graph: 그래프 내 어떤 두 vertex를 집어도 그 사이에 경로가 있는 것 <-> unconnected 한 쌍의 vertex라도 그 사이 경로가 없는 것
weighted graph: 연결된 엣지에 숫자나 값 부여한 것
경로의 길이: 경로를 따라 갔을 때 엣지에 써있는 weight의 합
-> 여러 경로가 있을 수 있음(shortest path는 길이가 최소화되는 경로)
directed graph: 방향이 있는 그래프
-> in_degree: 들어오는 엣지의 개수
-> out_degree: 출발하는 엣지의 개수
-> source: in_degree가 0인 vertex = 나로 들어오는 것은 없고 나가기만 함
-> sink: out_degree가 0인 vertex
-> strongly connected : 방향성을 인정했을 때 모든 pair간에 경로가 존재
-> weakly connected: 방향성을 무시하고 연결성을 따졌을 때 그래프가 연결되어 있음
directed acyclic(DAG): 방향이 있으나 cycle이 없음
그래프가 트리가 되는 경우
- 모든 경우가 connected 이고, 그 경로가 unique해야 함
- 엣지의 개수 = 노드의 개수 - 1
- cycle이 존재하지 않음
- 하나의 엣지를 제거 -> 이 트리는 disconnected, 서로 다른 그래프로 나눠져 두 개의 트리로 존재
forests: 트리들의 집합
- forest: cycle이 없는 그래프
- vertex 개수가 edge 개수보다 항상 많음
- 트리의 개수 = vertex 개수 - edge 개수
그래프의 표현
1) binary-relataion list
ex.{(1,2), (2,4),...}
- 엣지 개수만큼의 메모리 필요
- 연결 여부, neighbor 체크할 때 모든 경우 체크해야하므로 비효율적
2) adjacency matrix
ex. (1, 4) 연결되어 있으면 v*v 매트릭스의 (1,4)에 true (혹은 weight)
vertex 개수를 V개이면 V제곱개만큼의 메모리 사용
- neighbor 파악? (v,1) 부터 (v,v) 까지 확인해야 하기 때문에 V개 만큼의 오퍼레이션을 요구
- v1, v2의 연결 여부? (v1, v2)로 바로 접근 가능 __효율적
3) adjacency list
- 가장 많이 사용
- 각 vertex마다 연결된 엣지가 있는 vertex들을 리스트로 표현하는 형태
- 메모리? 전체 vertex 개수 만큼의 linked list 필요하고, 전체 데이터 개수를 따져보면 엣지의 개수를 넘어가지 않음(최대 vertex 혹은 엣지의 개수)
(강의 듣고 정리) k-mooc 인공지능을 위한 알고리즘과 자료구조: 이론, 코딩, 그리고 컴퓨팅 사고
