인접행렬을 이용한 그래프의 구현
소개
# 그래프를 정점 수 만큼의 행과 열을 갖는 정방행렬로 표현하는 방법이다.
# 그래프 G = (V,E)가 n개의 정점으로 구성되었다고 가정하면, 인접행렬A는 n*n의 2차원 배열로 표현한다. 즉, A = (i,j)
# 단순 그래프의 2차원 배열 A(i,j)의 원소는 간선(Vi,Vj)이 간선의 집합 E(G)에 속하면 A(i,j) = 1로 표시하고, 그렇지 않으면 A(i,j) = 0으로 표현한다.
# 다중 그래프의 2차원 배열 A(i,j)의 원소는 간선(Vi,Vj)이 간선의 집합 E(G)에 속하면 A(i,j) = n(간선의 개수)로 표시한다.
# 가중치 그래프라면 2차원 배열 A(i,j)의 원소에 가중치를 함께 표현할 수도 있다. 아래의 그림은 다중 가중치 방향성 그래프를 인접행렬로 표현했다.
# 이 인접행렬을 정점과 정점 사이의 관계를 표현하므로 node-to-node matrix라고도 부른다.
특징
# 리스트를 이용한 방법보다 구현이 비교적 쉽다.
# 두 정점 사이의 간선 유무나 가중치를 쉽게 파악할 수 있다.
# 정점의 차수를 쉽게 파악할 수 있다.
# 인접행렬로 표현하는 그래프가 방향성 그래프일 경우 행의 합이 진출차수(out-degree)가 되고, 열의 합이 진입차수(in-degree)로 계산하기 쉽다.
# 비방향성 그래프의 경우 대칭되므로 하삼각행렬이나 상삼각행렬만으로 표현 가능해서 저장공간이 낭비된다.
# 정점간에 연결되어 있지 않은 간선이 많아 연결이 느슨한 경우에는 저장공간이 낭비된다.
# 전체를 탐색하는데 O(n2)의 시간복잡도가 요구된다.
# 정점에서 정점으로의 모든 경로를 검색하는데에도 O(n2)의 시간복잡도가 요구된다.
# 가장 큰 문제는 정점을 추가할 경우, 배열을 새로 할당해야한다는 것이다.
# 그러므로 인접행렬을 사용해서 그래프를 표현하는 건 연결이 촘촘하고, 새로운 정점의 추가가 없는 경우에 권장된다. (간선을 추가하는 건 문제가 되지 않는다.)
실제 구현은 다음 포스팅에서 다룬다.