DFS와 BFS에서 인접행렬 vs 인접리스트

시간복잡도

• 인접행렬: O(V^2)
• 인접리스트: O(V + E) == O(max(V,E))
  • 정점의 개수와 간선의 개수 중 더 큰 값을 기준으로
  • 인접리스트는 간선의 개수가 적을수록 메모리 공간을 덜 잡아먹는 장점이 있었음
  • 만약 간선의 개수가 V에 비해 월등히 적으면 O(V)로 표현이 될 수 있음
  • 즉, 간선 개수가 적으면 인접리스트가 훨씬 유리해진다.