1. 인접행렬

행은 시작 인덱스, 열은 도착 인덱스
간선이 있는 부분은 1로 표기

무방향 그래프일 경우

대칭구조

2. 인접리스트

c++은 백터, python은 리스트 로 구현

무방향 그래프일 경우

인전행렬 vs 인접리스트

• 인접리스트는 인접행렬보다 더 적은 공간을 차지한다(메모리 절약) 간선이 적으면 적을수록 메모리측에서 유리

• 인접행렬은 공간을 많이 쓰는 만큼 실행시간에서 더 유리 할수 있다.
  ex) 인접행렬 은 A[0][3]의 위치를 알고 싶을 때 바로 검색이 가능하므로 시간복잡도가 O(1) 이다.
  ex) 인접리스트 같은 경우 연결 리스트 이기때문에 A[0][3]의 0행에 3이 있는지 하나하나 검색해야 하는 번거로움이 있다. 시간복잡도는 O(N) 이다.

정점 vs 간선