[GraphQL] 2장 그래프 이론

출처: yes24(http://image.yes24.com/goods/81537382/XL)

그래프 ( Graph )

그래프는 상호 연관 관계에 놓여 있는 객체 집합을 표현할 때 사용, 객체 간의 관계를 그래프라고 생각하면 편하다.

각 포인트를 노드(Node)나 정점(Vertex)라고 하고, 각 노드/정점을 잇는 선을 엣지(Edge)라고 한다.

그래프는 표현식으로도 나타낼 수 있다.

// 노드 or 정점
vertices = { 1, 2, 3, 4 }
// Edge
edges = {
	{1, 2},
	{1, 3},
	{1, 4},
	{2, 4},
	{3, 4},
}

위 표현식을 그림으로 나타내면 다음과 같이 그려진다.

시작 노드와 끝 노드의 구분 여부에 따라 그래프 종류를 구분할 수 있다.

무방향 그래프: 시작 노드와 끝 노드를 마음대로 정하면 된다. 특정한 번호 순서를 따르지 않는다. 비선형 데이터 구조

방향 그래프: 시작 노드와 끝노드를 구분할 수 없는 그래프. 노드 사이의 흐름(flow)이 존재한다. 에지를 표현할 때 소괄호를 통해 표현한다.

graph = (
	{1, 2, 3, 4},
	(
		{1, 2},
		{1, 3},
		{1, 4},	
	)
)

트리 그래프

트리(tree)는 노드가 위계적으로 정렬된 그래프. 루트 노드가 있으면 트리 그래프.

루트 노드로 시작되어 아래 자손 노드들이 연결되어있는 그래프 형태. ex) 조직도, 가계도

트리 그래프에서 엣지를 통해 하위 노드와 연결된다.

자식 노드를 가지고 있는 노드를 부모 노드라고 한다.

자식 노드 아래에 또 다른 자식 노드를 가지고 있으면 가지(branch)라고 한다.

자식 노드 아래에 더 이상 다른 자식 노드가 없으면 잎(leaf)라고 한다.

트리 그래프에서도 자식 노드를 최대 두 개까지 가지는 이진트리, 이진 탐색 트리가 있다.

이진 탐색 트리를 통해 효율적인 방식으로 데이터 탐색이 가능하다.

나무위키 참고해서 따라그림...