인접 행렬, 인접 리스트, 간선 리스트

 

인접 행렬

공간 복잡도: O(v * v)

인접 행렬을 사용하는 경우는 임의의 두 정점 사이에 간선이 있는지 없는지를 구할때 사용.

인접 리스트 (가장 많이 사용)

공간 복잡도: O(E)

한개의 정점과 연결된 모든 간선을 찾을 때 사용 (가장 많이 사용함)

공간도 시간도 가장 효율적으로 사용할 수 있음

간선 리스트

인접 리스트를 사용하기 싫은 경우, 간선 리스트를 사용한다

간선 리스트는 정렬해주는 과정 (cnt를 만드는 과정)이 필요하다.