인접 행렬

인접 행렬(adjacency matrix)은 그래프 이론에서 그래프를 표현하기 위한 방법 중 하나이다. n개의 정점이 있는 그래프에서 정점 i에서 정점 j로 가는 간선이 있을 경우에 $a_ij$를 1로 하고 없는 경우에는 0으로 표현한 $n \times n$ 크기의 인접 행렬로 표현할 수 있다. 인접 행렬의 특정 원소에 접근하는 데 걸리는 시간이 상수 시간이라면 정점 i에서 정점 j로 가는 간선이 있는지를 상수 시간에 알 수 있다. 정점의 개수를 n이라고 할 때 인접 행렬을 만드는 데 $O(n^2)$시간을 쓰게 되므로, 인접 행렬을 이용한 그래프 알고리즘의 시간 복잡도는 이보다 더 좋을 수 없다. 따라서 간선이 희소한 경우에는 인접 리스트 표현 방식이 유리하다.