그래프를 저장하는 방법

인접행렬(Adjacency Matrix)

2차원 행렬로 표현

//int n = 정점의 갯수
int[][] matrix = int new[n][n];

인접행렬의 공간 복잡도 : $O(v^2)$
-> 공간의 활용도가 낮고 메모리 이슈가 있음.

인접리스트(Adjacency List)

ArrayList<ArrayList<Integer>> list;

인접리스트의 공간 복잡도 : $O(E)$

• $O(min(deg(A),deg(B)))$ : 양방향
• $O(deg(A))$ : 단방향