그래프 탐색의 인접행렬과 인접리스트 비교

 

 

1. 인접행렬

• 장점
  • 행렬을 사용하기 때문에 공간지역성 특징으로 탐색 속도가 더 빠르다. 
  • 연결된 노드 중 특정 노드를 탐색하는 접근 속도 O(1) 
• 단점 
  • 위 그림처럼 O(N^2) 크기로 모든 노드 간에 간선 유무를 저장하게 된다. 
  • 방향성 있는 그래프라면 더욱 공간 낭비가 심해진다. 

 

2. 인접리스트

• 장점 
  • 꼭 필요한 간선만 표시하기 때문에 공간을 아낀다.
• 단점 
  • 리스트로 관리하에 속도가 느리다. 
  • 연결된 노드 중 특정 노드를 탐색하는 접근 속도 O(N) 

3. 비교 

• 노드 수보다 간선의 수가 많아질수록 추천 인접행렬 추천
  • 간선이 많아질수록 인접리스트의 공간을 아끼는 장점이 줄어든다. 

• 노드의 수가 노드 수보다 많을 때 인접 리스트 추천 
  • 공간을 아끼는 장점이 더욱 커진다.
• 기업 알고리즘 테스트에서는? 
  • 아직까지는 위 차이를 구분해서까지 문제를 푸는 경우는 없던 것 같다. (SDS Pro 시험 제외)
  • 필요하다면 주어진 테스트 입력에 대해 변환하는 과정을 거치고 알고리즘을 수행할 것 같다.