[알고리즘/이론]그래프의 표현

인접 리스트, 인접 행렬로 그래프를 표현할 수 있습니다. 이 두 방식은 방향, 무방향 그래프 모두에 적용할 수 있습니다. 대개 간선의 개수가 적으면 인접 리스트로 표현하며, 간선의 개수가 많은 경우 인접 행렬로 표현합니다. 보통 두 정점을 연결하는 간선이 있는지 빠르게 확인할 때는 인접 행렬을 사용합니다.

인접 리스트 표현법(adjacency-list representation)에서는 V개의 리스트로 그래프의 간선을 표현합니다. 각각의 리스트는 그래프 내의 하나의 정점에 대해 연결된 다른 정점들을 포함합니다.

무방향 그래프의 경우, (u,v)에 대해 u의 리스트와 v의 리스트 각각에 서로의 정점을 저장하고, 방향 그래프의 경우, u의 리스트에 대해 v 정점을 저장합니다. 따라서 무방향 그래프의 경우 리스트의 총 길이는 2*E이며, 방향 그래프의 경우 리스트의 총 길이는 E가 됩니다. 이에 따라 필요한 메모리의 공간이 Θ(V+E)라는 것도 확인할 수 있습니다.

그래프의 간선이 w(u,v)의 가중치를 갖는다면 그것 또한 인접리스트의 원소로 저장할 수 있습니다.

---

인접 리스트의 단점은 어떠한 간선이 그래프에 있는지 확인할 때 특정 리스트에서 해당 간선을 구성하는 데 필요한 정점을 검색해야만 합니다. 따라서 시간이 조금 오래 걸릴 수 있습니다.

인접 행렬 표현법(adjacency-matrix representation)은 V*V의 행렬을 활용하여 그래프의 연결상태를 표현하는 방법입니다. 행과 열은 각 정점을 나타내며 특정 원소에 1이 있다면 그 원소의 행과 열의 번호를 갖는 정점 사이에 간선이 존재한다는 것을 나타냅니다. 필요한 메모리 공간은 무방향, 방향 관계없이 Θ(V^2)이 필요합니다. 무방향 그래프의 인접 행렬의 경우, (u,v), (v,u) 모두 인접 행렬에 표현되므로 주대각선을 따라 대칭인 전치행렬의 형태를 가지게 됩니다. 가중치 그래프를 표현할 때는 각 원소에 1대신 가중치 w(u,v)를 저장합니다. 간선이 없는 경우라면 0, 또는 무한대 값을 대입하여 표현할 수 있습니다. 인접 리스트에 비해 소모되는 공간이 많지만 간선 검색이 간편하고 표현이 단순하여 적은 정점에 대해서도 많이 사용합니다.

그래프의 정점과 간선은 부가적인 속성을 가질 수 있습니다. 사용하는 프로그래밍 언어, 알고리즘, 그래프의 사용 방식에 따라 속성의 구현 방법은 달라질 수 있습니다. 또한, 반드시 정점이나 간선에 결합이 되어 하나의 요소로 존재해야 하는 것은 아닙니다. 부가적인 배열을 사용하여 속성을 표현할 수도 있습니다.