4. 그래프/tree

관계

- 일방적인 관계?

- 가중치

 

희소하다 sparse

- 인접행렬에서.. 100억개의 칸

- 간선이 10만개

- 10만개만 1이고 나머지는 0

- 대부분이 0

 

해시맵 

- 희소한 경우에는 해시맵이나, 트리맵을 쓰는 게 맞음

- 인덱싱이 되면 그냥 인접리스트 쓰면 되는데,

- 인덱싱이 안 되는 경우에는 해시맵을 쓰면 됨

---

DFS/BFS

BFS

- 가중치가 없는 그래프에서 시작노드에서 나머지 모든 노드까지 최단거리를 구할 때 사용

- 1>5나, 1>2, 3, 4, 5 구하는 것이나 시간 복잡도는 똑같음 

---

Tree

트리

- 두 정점을 잇는 단순 경로가 유일한 그래프

- 트리가 여러 개 있다면 -> 포레스트, (사이클이 없는 무방향 그래프)

 

조건?

- 모두 같은 연결 요소

- 사이클이 없음

- 노드 수 == 간선 수  + 1

rooted tree

binary tree

binary search tree