인접 행렬과 인접 리스트의 차이

공간복잡도

• 인접행렬 : O(V^2)
  bool adj[V][[V];

• 인접리스트 : O(V+E)
  vector<int> adj[V];

시간복잡도

간선 한 개 찾기

• 인접행렬 : O(1)
  (a[i][j])

• 인접리스트 : O(V) (최악의 경우 = 모든 정점이 연결되어 있을 때)

for(int j=0; j<adj[i].size(); j++) 
	adj[i][j]

모든 간선 찾기

• 인접행렬 : O(V^2)
• 인접리스트 : O(V+E)

💡[TIP]

• 그래프가 희소할 때는 : 인접리스트
  • 인접 행렬은 대부분의 요소가 0인데도 불구하고 메모리를 많이 써야 해서
• 그래프가 조밀할 때는 인접행렬
  • 메모리 차이는 거의 없고 i~j 간선 확인 속도가 더 빠르기 때문
• 보통은 희소한 그래프가 많이 주어지기 때문에 인접리스트를 쓰면 됨
• 다만 문제에서 인접행렬로 주어지면 인접행렬로 풀기