그래프의 표현
노드와 간선으로만 이루어진 데이터 구조.
리스트
저장공간 : 노드의 갯수 + 간선의 갯수(양방향이면 X2)
행렬
저장공간 : 노드의 갯수²
가중치 그래프의 표현
간선에 가중치가 표현된 그래프
리스트
가중치 값을 추가하여 기록한다.
행렬
가중치를 행렬 값에 넣어준다.
리스트와 형렬 비교
저장공간
- 값이 성기면 리스트가 유리함.
- 값이 촘초하면 행렬이 유리함.
간선을 찾는데 걸리는 시간
- 리스트 : O(노드갯수)
- 행렬 : O(1)
모든 간선을 찾거나 방문하는데 걸리는 시간
- 리스트 : O(노드갯수+간선갯수)
- 행렬 : O(노드갯수²)
출처
'알고리즘 > 알고리즘' 카테고리의 다른 글
| 깊이 우선 탐색 Depth-first search (0) | 2021.09.19 |
|---|---|
| 너비 우선 탐색 Breath-first Search BFS (0) | 2021.09.19 |
| 힙 정렬 Heap Sort (0) | 2021.09.19 |
| 병합정렬 Merge Sort (0) | 2021.09.19 |
| 삽입정렬 Insertion Sort (0) | 2021.09.19 |