[CS] Graph, Tree

트리 ⊂ 그래프

 

그래프

노드(하나의 점)와 노드 간을 연결하는 간선으로 구성된 자료 구조이다. 순환 혹은 비순환 구조를 이룬다.

그래프의 구현 방법은 2가지 방식이 있습니다.

- 인접 행렬(adjacency matrix) : 2차원 배열을 사용하는 방식

- 인접 리스트(adjacency list) : 리스트를 사용하는 방식

두 방식의 메모리와 속도 차이는 다음과 같습니다.

V : 노드의 개수, E : 간선의 개수 일 때, 

인접 행렬은 O(v^2), 인접 리스트는 O(E) 만큼의 메모리 공간이 요구됩니다.

인접 행렬은 O(1), 인접 리스트는 O(V)만큼의 시간이 소요됩니다.

 

트리

그래프와 같이 노드와 노드 간을 연결하는 간선으로 구성된 자료 구조이다.

트리는 두 개의 노드 사이에 반드시 1개의 경로만을 가지며 사이클이 존재하지 않는 방향 그래프이다.

이러한 특성 때문에 '최소 연결 트리'라고 부르기도 한다.

 

	그래프	트리
정의	노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조	그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류
방향성	방향 그래프(Directed) 무방향 그래프(Undirected) 모두 존재	방향 그래프(Directed Graph)
사이클	사이클(Cycle) 가능, 자체 간선(Self-Loop)도 가능, 순환 그래프(Cyclc), 비순환 그래프(Acyclic) 모두 존재	사이클(Cycle) 불가능, 자체 간선(Self-Loop)도 불가능, 비순환 그래프(Acyclic Graph)
루트 노드	루트 노드의 개념이 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 가짐
부모 - 자식	부모- 자식의 개념이 없음	부모-자식 관계 top-bottom , botton-top으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 안의 Pre-, In-, Post-order (전위, 중위, 후위 순회)
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1개의 간선을 가짐
경로	-	임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목	이진 트리, 이진 탐색 트리, 균형 트리(AVL트리, Red-Black트리), 이진 합(최대 합, 최소 합) 등