그래프

1. 그래프의 표현

인접 행렬(Adjacency Matrix) : 공간 복잡도 O(V^2), 작은 크기의 밀집 그래프에서 유리 희소 그래프에서 불리,이웃한 정점을 나열하는데 O(V)

인접 리스트(Adjacency List) : 공간 복잡도 O(V+E) 이웃 정점의 번호, 가중치로 표현. 이웃한 정점을 나열하는데 유리

간선 리스트(Edge List) : 공간 복잡도 O(E), MST를 구하기 위한 크루스칼 알고리즘에서 요긴. 인접한 간선을 나열하는 데 불리

한 정점의 이웃을 살펴보는데 : O(V) vs O(k) vs O(E) 
그래프 탐색(DFS, BFS) : O(V * V = V^2) vs O(V∑k = V + E) vs O(V * E = VE)

결론 : 탐색 시 인접 리스트가 가장 유리