정의
인접 행렬은 그래프의 연결 관계를 이차원 배열로 나타내는 방식
인접 리스트는 각각의 정점에 인접한 정점들을 리스트로 표현한 방식
이런 그래프가 있을 때 각각의 방식으로 표현한다면
| 1 | 2 | 3 | 4 | |
| 1 | 0 | 1 | 1 | 1 |
| 2 | 1 | 0 | 0 | 1 |
| 3 | 1 | 0 | 0 | 0 |
| 4 | 1 | 1 | 0 | 0 |
인접 행렬은 이런 방식으로 표현되고
1: 2, 3, 4
2: 1, 4
3: 1
4: 1, 2
인접 리스트는 이런 방식으로 표현된다.
장단점
인접 행렬
- 그래프에 간선이 많은 밀집 그래프의 경우 유리하다.
- 장점
- 두 정점을 연결하는 간선의 존재여부를 O(1)안에 알 수 있다.
- 정점의 차수를 O(N) 안에 알 수 있다.
- 단점
- 인접 행렬 전체를 검사할때 O(n^2)가 필요하다.
인접 리스트
- 그래프에 간선이 적은 희소그래프의 경우 유리하다
- 장점
- 인접 행렬 전체를 검사할때 O(N+E)안에 알수 있다.
- 단점
- 간선 존재여부, 정점의 차수를 아는데 정점의 차수 만큼의 시간이 필요하다.
References
gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
[자료구조] 그래프(Graph)란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
[그래프] 인접 행렬과 인접 리스트
그래프 관련 문제를 풀 때는, 문제 상황을 그래프로 모델링한 후에 푸는 것이 보편적입니다. 이 때, 모델링한 그래프의 연결관계를 나타내는 두 가지 방식이 있습니다. 1. 인접 행렬 2. 인접 리스�
sarah950716.tistory.com
'CS > 자료구조' 카테고리의 다른 글
| 이진탐색트리의 순회 (0) | 2022.02.04 |
|---|