정점과 간선으로 이루어진 자료구조
여러 가지 그래프
방향 그래프
순환 그래프
비 순환 그래프
완전 그래프
연결 그래프
단순 그래프 : 두 정점 사이의 간선이 1개 이하이고 루프가 존재하지 않는 그래프
루프 예시)
인접 리스트
간선이 상대적으로 작아 인접 행렬에 비해 공간을 절약 할 수 있다.
구현)
STL 없이 구현해야 할 경우
| 인접 행렬 | 인접 리스트 | |
|---|---|---|
| 공간 복잡도 | O(V^2) | O(V+E) |
| 정점 u, v가 연결되어 있는지 확인하는 시간 복잡도 | O(1) | O(min(deg(u), deg(v)) |
| 정점 v와 연결된 모든 정점을 확인하는 시간 복잡도 | O(V) | O(deg(v)) |
| 효율적인 상황 | 두 점의 연결 여부를 자주 확인할 때 E가 V^2에 가까울 때 | 특정 정점에 연결된 모든 정점을 자주 확인할 때 E가 V^2보다 훨씬 작을 때 |