그림 6-13은 인접 행렬을 어떻게 표현할지 보여 줍니다. 각각의 행을 정점으로 보고 열을 자신을 포함한 다른 정점이라고 생각하면 (1행, 2열)은 정점 1과 정점 2 사이의 관계를 나타냅니다. 그림 6-13을 보면 해당 값이 0이군요. 이 값은 정점 1과 정점 2는 서로 인접하지 않다는 것을 의미합니다. 이차원 배열을 adj_matrix라고 합시다. 에지 (0, 1)이 있다면 adj_matrix[0][1]이 1이고 없다면 0입니다. 배열을 보면 adj_matrix[0][1]이 1이므로 에지 (0, 1)이 있습니다. 또 다른 특징을 살펴보면 그림 6-13은 그래프가 무방향 그래프입니다. 그러므로 (0, 1)과 (1, 0)이 행렬에서 모두 1입니다. 즉, 이 행렬은 대각선에 대해 대칭입니다.

인접 리스트에서 살펴보았던 두 가지 연산에 대해 인접 행렬은 어떤 빅오를 가지는지 보겠습니다. 먼저 정점 v에 대해 인접한 모든 노드를 탐색하는 연산입니다. 이 경우 v행에 대해 모든 열을 검사해야만 합니다. 즉, 열 개수는 정점 개수이지요. 정점 개수를 n이라고 했을 때 O(n)입니다. 두 번째 연산인 (u, v)가 있는지 여부를 확인하는 연산은 어떤가요? adj_matrix[u][v]를 확인만 하면 되므로 O(1)입니다.

그래프의 두 가지 표현 방법을 모두 알아보았으니 이제 직접 그래프를 구현해 보겠습니다. 먼저 이번 예제에서는 무방향 그래프를 인접 리스트로 표현해 보겠습니다.