알고리즘 7장
그래프 모델: 간선 존재 질의 비교
간선 존재 질의가 많다면 인접 리스트와 인접 행렬의 조회 비용과 메모리 비용을 함께 비교해야 합니다.
상태 변화
표현 비교
list
memory O(V+E)
list query
O(deg u)
matrix
memory O(V²)
matrix query
O(1)
불변식
점검
인접 리스트
메모리 O(V+E), 간선 존재 확인은 이웃 수에 영향을 받습니다.
인접 행렬
메모리 O(V^2), 간선 존재 확인은 O(1)입니다.
희소 그래프
E가 V^2보다 훨씬 작으면 리스트가 보통 유리합니다.
밀집 그래프
존재 질의가 잦고 메모리가 허용되면 행렬을 고려합니다.