자료구조
그래프 개념
grape.store
2022. 1. 25. 00:05
반응형
G = (V,E)
G = graph, V = vertex(점), E = edge(선)
그래프란?
- 정점과 간선으로 이루어진 자료 구조
그래프의 표현법
1. G의 인접행렬
- 메모리 사용량 O(V^2)
- 한정점에 연결된 간선을 모두 순회할 때, 항상 O(V)의 사간을 사용
- 정점에 비해 간선이 몇 개 없는 그래프에서 비효율적으로 작동
- 메모리 사용량이 많음, 작은 메모리의 유리
2. 인접리스트
- 메모리 사용량 O(V+E)
- 메모리 사용량이 적으며, 희소 그래프를 표현하는 데 유리
- 한 정점에서 시작하는 간선을 모두 순회할 때, 연결된 정점의 개수만큼의 시간을 소요