# Graph

Graph 를 표현하는 2가지 방식
---
- 인접 행렬- 2D Array : 공간 낭비가 심함 / 시간 복잡도가 O(n^2) / undirected 인 경우 diagonal (대각선) 을 기준으로 대칭임.
- 인접 리스트 - Linked List: 공간을 효율적으로 사용할 수 있음 / 시간 복잡도와 공간복잡도가 O(V+E)
- 둘 중에 어떤 것을 쓸까 생각해보면, edge 수가 많은 경우 matrix를 쓰는게 좋다. 왜냐하면 공간과 시간이 인접리스트에 비해서 그렇게 소모되진 않으니까. 또한, prim's 알고리즘이나 다익스트라 알고리즘을 사용하는 경우 코드의 간결함을 위해서 배열을 쓰는 경우가 있다.
- 하지만. 그 외의 경우네는 인접리스트가 시간 복잡도나 공간 복잡도가 인접 행렬에 비해서 적은 편이기 때문에 사용하는 것을 권장한다

Tree 와 Graph 의 차이
---
- Tree 는 Graph의 제한된 형태. 즉, Tree는 Graph 의 부분집합임. 모든 Tree 는 Graph 이지만, 모든 Graph 는 Tree가 아님

Graph의 사례
---
- Map 은 그래프를 사용해서 표현될 수 있고, 두 도시 사이의 최단거리를 찾는 알고리즘이 필요한 서비스에서 사용 가능
- Topological sort를 통해서 의존성이 있는 여러 업무들에 대한 정렬을 할 수 있음
- 현재 state 에서 legal 한 move가 무엇인지 나타내는 state diagram 에 사용될 수 있음.
- 소셜 네트워크

Bipartite 그래프란?
---
- Vertex 들이 두 개의 독립적인 집합으로 구분될 수 있는 그래프를 bipartite 그래프라고 부름.
- Vertex가 주어졌을 때 bipartite인지 아닌지 알아볼 수 있는 방법은? BFS 와 coloring 을 사용하자
1. Source 를 red 로 색칠한다
2. 인접한 모든 노드들을 blue로 색칠한다
3. 거기서 또 인접한 노드들을 red 로 색칠한다
4. 만약 색칠하려고 하는데 내가 blue 인데 이웃도 blue 로 칠해야하는 경우가 오면 bipartite 가 아니라고 판단할 수 있음.

**DFS 로도 역시 bipartite 인지 구분할 수 있음*

그래프의 활용 사례
---
- Os 의 resource allocation graph
- Airline system 의 effective route optimization
- Maze problem
- DAG((Directed Acyclic Graph)

그래프의 장점
---
- Shortest path 를 알 수 있음
- Neighbors of nodes 를 알 수 있음
- DFS 와 BFS 와 같은 알고리즘을 사용할 수 있음.

그래프의 단점
---
- Pointer 를 너무 많이 사용하여 다루기 복잡함
- 메모리 사용량이 많음
- 인접행렬로 만들면 graph 의 multiplication 이나 parallel edge 를 사용하기 어려움