인접성 확인
인접 행렬
(1) 방향이 없는 그래프
공간 복잡도
시간 복잡도
정점의 차수(degree)를 계산하는 데에 걸리는 시간. 정점 a가 자신과 연결된 간선이 몇개인지 확인하는 시간 n-1
그리고 이걸 모든 정점에 대해 확인 n
->
그래프 전체의 인접성을 계산하는 데에 걸리는 시간 n(n-1)
그 대각선빼고 행렬 만드는 거면 당연히 n(n-1) 이겠지
(2) 방향 그래프
인접 리스트
linked list
시간복잡도
링크드리스트 만드는 시간 복잡도는 n개 포인터 만들고, 정점만큼 더 만들어야하니까 n+e or n+2e(무방향)
솔직히 잘 이해 안 감
array
aList[1]=(2,4)
정점 1과 인접한 정점 2,4
