Graph와 Tree란?

1. 그래프란?

정점(노드)와 정점을 연결하는 간선으로 구성된 자료구조입니다.  
계층이 없는 네트워크 모델이며, 싸이클(순환)이 존재할 수도, 존재하지 않은 수도 있습니다.  
연결되어 있는 객체간의 관계를 표현할 수 있느 자료구조입니다.

2. 트리란?

그래프이 종류 중 하나로, 노드와 간선으로 이루어진 비선형 자료구조입니다.  
루트 노트가 존재하고, 부모-자식 관계로 이루어진 계층적인 모델입니다.  
노드와 노드는 단 하나의 간선으로 연결되어 있으며, 싸이클이 존재하지 않습니다.

3. 그래프와 트리의 차이?

 그래프
- 노드 사이에 둘 이상의 경로가 가능하다. (단방향, 양방향 가능)
- self-loop와 circuit(순환)이 가능하다.
- 루트노드와 부모-자식이라는 개념이 없다.
- 순회는 BFS나 DFS로 이루어진다.
- 간선의 유무(개수)는 그래프마다 다르다.
- 네트워크 모델

 트리
- 노드 사이에 하나의 경로만 가능하다.
- circuit가 없다.
- 한 개의 루트 노드가 존재하며, 모든 자식노드는 하나의 부모노드를 가진다.
- 순회는 Pre-order, In-order, Post-order로 이루어진다.
- 간선은 항상 (정점-1)개이다.
- 계층 모델 (깊이와 높이라는 개념 존재)

4. 그래프의 구현방법?

1) 인접 행렬
- 2차원 배열에 정점들의 연결관계를 저장.
- (N x N) 배열이 생성되므로, 간선의 개수에 상관없이 n^2의 공간을 필요
- 연결 정보(혹은 간선)를 O(1)만에 탐색 가능
- 순회를 할 때에는 배열을 전부 탐색해야 하므로, 간선이 많은 경우 효율적.
- ⇒ 정점과 정점간의 간선을 자주 탐색할 때 2) 인접 리스트 
- 정점객체에 인접한 정점의 리스트를 저장많은 밀집 그래프(행렬)이라면 => 인접 행렬 E(간선의 개수)만큼의 공간을 필요 (m+2n or m+n)
- 정점의 번호를 안다면, 인덱스(==번호)로 인접한 정점의 리스트에 쉽게 접근가능

     O(n+e) (노드의 개수 + 간선의 개수)

- 간선의 개수에 필요공간이 좌우되므로, 노드와 간선이 적은 그래프일때 용이
- ⇒ 하나의 정점을 기준으로 연결된 간선을 탐색할 때 유리함.

+ 공간복잡도
    - 인접 행렬은 n^2의 공간을 필요
    - 인접 리스트는 e의 공간필요
    즉, 간선의 개수 적은 희소 그래프(행렬)이라면 => 인접 리스트
    간선의 개수 e가 많은 밀집 그래프(행렬)이라면 => 인접 행렬