Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
Tags
- MySQL
- Interceptor
- OOP
- Deep Dive
- Spring
- javascript
- 프로그래머스
- nestjs
- TIL
- Kubernetes
- html
- 인접행렬
- 인접리스트
- LifeCycle
- 알고리즘
- puppeteer
- typescript
- java
- css
- REST API
- dfs
- GraphQL
- 코딩테스트
- node.js
- bean
- 자료구조
- 탐욕법
- winston
- Linux
- JWT
Archives
- Today
- Total
처음부터 차근차근
[자료구조] 인접 행렬, 인접 리스트 본문
728x90
Graph 관련 문제를 해결하기 위해 모델링할 경우에는, 두 가지 방법이 존재합니다.
- 인접 행렬
- 인접 리스트
인접 행렬
- 그래프에서 정점과 간선의 관계를 나타내는 bool 타입의 정사각형 행렬을 의미한다.
- 정사각형 행렬의 각 요소가 0 또는 1이라는 값으로 가짐을 의미하며, 0은 두 정점 사이의 경로가 없음을 의미하며, 1은 두 정점 사이의 경로가 있음을 의미한다.
간단히 요약하자면 다음과 같다.
adj[i][j] = 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
다음 그래프를 한번 살펴보자
- 1 - 1, 2 - 2를 보면 0으로 되어있는 것을 볼 수 있는데 자기자신을 나타내는 것이며 해당 정점의 사이클이 없을 때는 0, 사이클이 있을 때는 1로 표기를 합니다.
- 0 - 1 이 연결되어있기 때문에 a[0][1] = 1이 됩니다. 그러나 1 - 3은 연결되어있지 않기 때문에 a[1][3] = 0이 됩니다.
이것을 C++ 코드로 표현하자면 이렇게 된다.
bool a[4][4] = {
{0, 1, 1, 1},
{1, 0, 1, 0},
{1, 1, 0, 0},
{1, 0, 0, 0},
};
장단점
인접 행렬의 장점으로는
- 구현이 쉽다.
- adj[i][j]가 1인지 0인지만 확인하면 되기 때문에 시간 복잡도는 O(1)이다.
단점으로는
- 모든 간선을 찾기 위해서는 O(V^2)라는 시간 복잡도가 걸린다.
- 또한 간선이 적은 경우에도 2차원 배열을 만들기 때문에 메모리를 더욱 많이 사용한다.
인접 리스트
- 인접 리스트는 그래프에서 정점과 간선의 관계를 나타내는 연결리스트를 의미한다.
- 인접 리스트는 연결리스트로 구현한다. (C++에서는 vector로 구현하거나, Javascript에서는 Array로도 구현 가능하다.)
인접 행렬에 있는 예시를 인접 리스트로 구현한다면 다음과 같게 된다.
{
0 : [1, 2, 3],
1 : [0, 2],
2 : [0, 1],
3 : [0]
}
장단점
장점으로는
- 실제로 연결된 노드에 대한 정보만 저장하기 때문에, 간선의 개수에 비례하는 메모리만 차지한다.
단점으로는
- 노드 i와 노드 j가 연결되어 있는지 확인하는 시간복잡도는 O(N)이 걸린다.
인접 행렬과 인접 리스트 비교
참조
https://sarah950716.tistory.com/12
https://suyeon96.tistory.com/32
'CS > 자료구조' 카테고리의 다른 글
[자료구조] Tree (0) | 2023.11.16 |
---|---|
[Javascript] 인접행렬, 인접 리스트 구현 방법 (0) | 2023.11.15 |
[자료구조] Graph (0) | 2023.11.15 |
[TypeScript] MaxHeap 구현 (0) | 2023.11.13 |
[자료구조] Heap (0) | 2023.11.13 |