그래프 표현

인접행렬(adjacency matrix)
행렬을 사용하여 나타낸다.
ex> (v1. v2)가 존재한다면 matrix[1][2] = 1, 존재하지 않으면 값은 0이된다.

필요한 기억장소의 크기 = 공간복잡도(space complexity) = S(n) = n제곱
무방향 그래프에서는 행렬이 대각선을 중심으로 대칭(symmetric)이다.

이는 완전 그래프를 제외하고는 대부분의 그래프일 경우 edge 수는 적기 때문에 대부분의 행렬원소들은 0이 된다. 고로 상당량의 기억장소가 낭비된다.


인접리스트(adjacency list)