이러한 규칙에 따라 그림 2-2의 그래프를 인접 행렬로 표현하면 표 2-1이 된다. 이 표를 보면 인접 행렬은 대칭이라는 것을 알 수 있다. 또한, 대각선은 그래프에 루프가 있는 경우를 제외하고 모두 0이 된다. 행렬을 A라고 하면 임의의 노드 i 와 j에 대해 모든 무방향 그래프에서 Aij = Aji다. 하지만 방향 그래프에서는 노드 i 에서 노드 j로의 간선과 노드 j에서 노드 i로의 간선이 모두 있지 않으면 이 식은 성립하지 않는다. 또한, 행렬에서 값이 0인 것이 많은데, 이것은 희소 그래프의 전형적 모습이다.
▼ 표 2-1 그림 2-3 그래프의 인접 행렬
|
0 |
1 |
2 |
3 |
4 |
5 |
|
|
0 |
0 |
1 |
0 |
0 |
0 |
0 |
|
1 |
1 |
0 |
1 |
0 |
0 |
1 |
|
2 |
0 |
1 |
0 |
1 |
1 |
0 |
|
3 |
1 |
0 |
1 |
0 |
1 |
0 |
|
4 |
0 |
0 |
1 |
1 |
0 |
1 |
|
5 |
0 |
1 |
0 |
0 |
1 |
0 |
그래프가 성기지 않더라도 인접 행렬에서 값이 0인 원소들 때문에 공간이 낭비되는 것을 경계해야 한다. 공간을 낭비하지 않으려고 더 적은 공간을 사용하는 대안적 그래프 표현법이 있다. 현실 세계 그래프에는 수백만 개의 간선이 있을 수 있으므로 대부분 공간을 절약하고자 대안으로 배열(array)을 사용하여 그래프의 정점을 표현한다. 배열의 각 원소는 하나의 정점을 나타내고 해당 정점의 이웃이 되는 정점들을 포함한 리스트(list)의 시작이 된다. 이 리스트를 그래프 내 정점의 인접 리스트(adjacency list)라고 부른다.