트리
1. 그래프 종류 중 하나인 '트리'
순환성이 없는 무방향 또는 방향 그래프
- 특정하지 않는 한, 어떤 노드이던지 루트가 될 수 있다.
- 가장 바깥쪽 노드를 리프노드라고 한다.
- 노드 a에서 노드 b로 가는 방향은 반드시 존재한다.
- 노드개수는 간선개수보다 한개 더 많다.
방향이 있는 트리라면, 부모->자식 관계를 나타낸 것이다.
* 문제에는 주로 방향성이 있는 트리가 더 많이 나올 것이다.
2. 코드로 그래프를 나타내는 법
덱, 힙과 달리 그래프는 따로 제공되는 라이브러리가 없다.
직접 구현을 해야한다.
이걸 구현하는 방법은 몇가지가 있다.
2-1. 인접행렬로 구현하는 방식
| 0 | 1 | 2 | 3 | |
| 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 1 | 0 |
세로에 적힌 쪽이 '출발 간선'의 정보이고,
가로에 적힌 족이 '도착 간선'의 정보이다.
만약 양방향 그래프라면, 한쪽이 채워질때 반대쪽도 채워지게 될테니 대칭행렬이 된다.
2-2. 인접리스트로 구현하는 방식
| 0 | 1 | 2 | 3 | ||
| 1 | 2 | ||||
| 2 | |||||
| 3 | 2 |
0과 연결된 노드들에 대한 리스트, 1과 연결된 노드들에 대한 리스트.. 이렇게 각각의 리스트를 만든다.
만약 양방향 그래프라면, 0 리스트에 1 이 있다면, 1 리스트에도 0 이 있을 것이다.
*문제 ) 두 가지 방법이 있다면 둘 중에 하나를 골라서 써야하는데, 어떤걸 써야할까.
인접행렬 vs 인접리스트 판단 기준
비교 - 인접 행렬이 인접리스트보다 훨씬 더 공간을 많이 차지함.
이유 - 노드가 n 개면, n 제곱 만큼 무조건 쓰게됨. 연결되지 않은 노드들에 대한 정보도 '0'으로 표시해야하기 때문.
인접리스트는 간선 개수가 적으면 적을수록 메모리 차지하는게 굉장히 적어짐.
노드가 n 개이더라도, 간선 개수가 적으면 메모리 적음.
인접행렬의 장점은? 시간과 공간이 trade off 니까, 대신 시간 측면에서는 유리함.
임의 접근을 이용해서 검색 가능.
예를 들어, 0에서 3으로 간선이 있는지 확인하는 경우를 생각해보자.
인접행렬이라면, G[0][3] 으로 바로 접근이 가능하다. -> o(1)
인접 리스트라면, 0번 리스트에서 첫번째 요소부터 시작하여 해당 요소가 3인지 확인해보아야 한다. -> o(n)
결론: 시간 -> 인접 행렬 win, 공간 -> 인접 리스트 win.
정점 개수와 간선 개수가 최대 몇개까지 주어지는 확인.
대부분 둘 중 뭘쓰던 통과되는 문제가 많지만, 둘 다 쓸 줄은 알아야함.
정점이 N개일 때,
최대 간선 개수가 많다면(N 제곱), 인접 행렬보다 인접리스트를 쓰는게 유리할 수 있음.
적다면 (2N), 인접 행렬을 쓰는게 유리할 수 있음.