Edge list
A[2][N]
노드를 배열에 저장하여 에지를 표현
배열에 출발 노드, 도착 노드, (가중치) 를 저장
>
- 특정 노드와 관련 있는 에지를 탐색하기는 쉽지 않음
- 노드 중심 알고리즘 x
- 벨만 포드 / 크루스칼 사용
Adjacency matrix
A[N][N]
노드 중심의 그래프 표현
- 노드와 관련된 에지 탐색시 N번 접근해야 하므로, 노드 개수에 비해 에지가 적을 때는 공간 효율성이 떨어짐
- 노드 갯수가 많은 경우 2차원 배열 선언이 불가한 결함(노드가 3만개가 넘으면 heap space 에러 발생)
Adjacency List
ArrayList<Integer>[N]
- 노드 개수만큼 ArrayList를 선언
- 에지 탐색 시간은 빠름
- 노드 개수가 커도 공간 효율이 좋아 메모리 초과 에러도 발생하지 않음
'Hard deck > Module' 카테고리의 다른 글
| topology sort (0) | 2022.08.15 |
|---|---|
| union-find (0) | 2022.08.15 |
| 다중 공간 추측하기 (0) | 2022.08.06 |
| Triangle Circulation (0) | 2022.08.06 |
| Extended Euclidean (0) | 2022.08.04 |