non-linear data structure (일직선이 아닌 구조)
내비게이션이나 경로등 최단, 최소 비용 찾기에 좋은 자료구조
한 vertex(꼭지점)에 2개 이상의 경로가 가능
점과 점을 연결해주는 간선은 edge
노드들 사이에 무방향, 양방향 경로를 가질 수 있음
자기 자신을 가르키는 self loop, 시작과 끝이 같은 loop cycle 가능
순환과 비순환으로 나뉜다.
vertex에서 직접적으로 이어져 있는 vertex들을 인접 버텍스라고 하고,
그 선들을 디그리(degree)라고 표현
(ex) A가 B,C,D랑 이어져 있다고 가정했을때,
A의 인접버텍스는 3개, B,C,D의 인접버테스는 1개이다.
방향성이 없는 경우 그선들을 디그리라고 표현
방향성이 있을때는 A에서 B로가는 엣지를 outdegree(진출차수),
B, C, D에서 A로 가는 엣지를 indegree(진입차수)
그래프 구현방식은 두가지 방법이 있다
인접리스트(Adjacency list), 인접 행렬(Adjacency Martrix)
2차원 배열에 모든 버텍스의 연결 관계를 담는 방식
버텍스와 버텍스간의 엣지를 자주 탐색할때 쓰는 방식
0과 1을 이용한 정수 행렬로 표현 가능
if(간선[a][b] === 1) // 연결
if(간선[a][b] !== 1) // 연결되어있지 않음
NxN으로 만들어지기때문에, 간선의 수와 무관하게 n^2메모리 공간이 필요함
버텍스를 잇는 엣지의 여부를 O(1)안에 찾을 수 있는 장점이 있지만, 순회를 - 해야될때는 전부 다 돌아야 되기 때문에 그래프에 간선이 많은 밀집 그래프일때 좋다
버텍스 객체 안에 버텍스 리스트를 저장,
버텍스의 번호를 알게된다면 이 번호를 배열의 인덱스로해서 각 버텍스의 리스트에 쉽게 접근 가능 (무방향에서는 두번씩 저장해야 서로 이어질수 있다)
인접 노드를 쉽게 찾을 수 있고, 그래프에 존재하는 모든 간선의 수를 O(n+e)안에 알 수 있다. 인접행렬보다 메모리 차지 비중이 크기 때문에 그래프 내에 적은 숫자만을 가지는 그래프에 용이.
하나의 버텍스를 기준으로 탐색을 자주할때 용이
시잠점을 루트라고표현. 부모노드에서 자식노드로 뿌리를 내리는 형식
같은 부모 노드에 자식노드들을 묶어서 부를때는 형제 노드라 부른다
더이상의 자식노드가 없는 노드는 리프 노드라고 부른다
노드가 N개인 트리는 항상 N-1개의 엣지를 가지게 되고, 트리 루트에서 뻗어져 나오기 때문에 루트에서 어떠한 경로로 가는 경로는 유일하다.
트리의 height은 루트로 부터 얼마만큼 내려와 있는지를 확인
트리의 깊이는 요소에서부터 시작. 요소에서부터 루트까지의 거리를 재는것.
트리안에서의 특정 노드의 깊이
(complete binary tree)
: 트리의 모든 높이에서 노드가 꽉 차 있는 모든 트리.
마지막 노드를 제외한 모든 노드들이 두개씩 채워져있음. 만약 하나가 비워져 있다고 하더라도 오른쪽이 비워져 있어야함
(Full binary tree)
: 모든 노드가 0개 또는 2개의 자식노드를 가지고 있어야한다. 1개를 가지고 있는 것은 정이진 트리가 아니다.
( Perfect Binary tree)
: 완전과 정 이진을 합친 트리, 마지막을 제외한 모든 노드가 두개의 자식 노드를 가져야 한다 .