[그래프] #2 인접 행렬과 인접리스트

인접 행렬

인접 행렬(Adjacency matrix) 그래프를 나타내기 위한 방법 중 하나로, 다른 방법으로는 인접 리스트(Adjacency list)가 있습니다. 인접 행렬의 \((i,j)\) 항은 정점 \(i\)로 부터 \(j\)로 뻗어 나가는 간선의 개수입니다.

무향 그래프

왼쪽의 그래프와 인접 행렬을 보면 알 수 있듯이, 무향 그래프에서의 인접 행렬은 대칭 행렬입니다. 이에 반해서, 유향 그래프의 인접 행렬은 대칭 행렬이 아닐 수 있습니다. (모든 간선에 대해 그 간선의 역방향 간선이 존재한다면, 인접 행렬이 대칭 행렬이 된다.) 

 

인접 행렬의 유명한 성질 중 하나는 행렬의 n승의 항이 정점 i에서 j로의 n개의 간선을 이용하는 보행의 수입니다.

이는 무향 그래프이든 유향 그래프이든 관계없이 성립하게 됩니다. 행렬의 제곱을 생각해보면, (i에서 j로의 보행의 수) × (j에서 k로의 보행의 수)가 (i, k)의 항이 되게 된다는 것에서 이가 성립하는 이유를 충분히 생각해낼 수 있습니다.
 또한, 유향 그래프의 인접 행렬의 전치 행렬이 나타내는 그래프는 원래 그래프에서 간선의 방향만 반대가 된 그래프입니다.

위 그래프의 인접 행렬

인접 리스트

인접 행렬을 생각해보면, 그래프 관련 알고리듬에서의 시간 복잡도가 \(O(N^{2})\)보다 작을 수 없다는 단점이 있습니다.

이는 인접 행렬이 각 정점에 인접한 다른 정점들을 알아내는 것이 상당히 비효율적이기 때문입니다.

 

  인접 리스트는 각 정점에 대해 인접한 정점들을 그 정점들에 나열한 배열입니다. 또한, 유향 그래프에서 인접 리스트는 특정 정점에서 다른 정점들로 간선을 하나만 이용하여 갈 수 있는 정점들을 나열한 배열입니다. 인접 리스트를 이용하면, 그래프의 탐색 등에서 시간 복잡도를 인접 행렬을 이용하는 것보다 훨씬 빠르게 할 수 있습니다.

 

물론 인접 행렬이 항상 인접 리스트보다는 못하지는 않습니다. 두 정점 간의 인접성을 나타내는 데에는 인접 행렬이 더 우수하며, 완전 그래프에서는 탐색에서도 두 가지 표현 방식의 이론적인 시간 복잡도는 다르지 않습니다.

하지만, 보통 인접 리스트가 더 효율적이며, 작은 크기의 그래프에서 훨씬 많은 양의 간선을 이용하는 보행의 수를 얻어야 하는 경우는 거의 없습니다.