[그래프의 표현] 인접행렬과 인접리스트
그래프(Graph) 란 자료구조의 일종으로
크게 정점 (Node, Vertex) 와 간선(Edge) 두가지의 구성요소를 가지고 있다.
.png)
위 그림에서 1,2,3으로 표시된 원은 정점을 나타내는 것이고, 파란색 화살표는 간선을 표현하는 것이다.
우리는 이러한 그래프를 코드화하여서 표현해야 하는데, 크게 그래프를 코드화하여 표현하는데는 두가지 방법이 있다. 첫 번째는 인접 항렬 (Adjacency-matrix)이고 두 번째는 인접 리스트(Adjacency-list) 이다.
1) 인접 항렬 (Adjacency-matrix)
인접항렬은 정점의 개수를 V라고 했을 때 V*V 크기의 배열을 이용하는 방법이다.
정점 i에서 정점 j 로 가는 간선이 있을 경우 A[i][j]=1로 표현하고 간선이 존재하지 않을 경우 A[i][j]=0으로 표현한다.
여기서 중요한 점은 그래프에 방향이 있는지, 없는지 방향의 유무이다. 방향이 없는 그래프도 많이 존재하는데 그 경우에는 정점 i에서 정점 j로 가는 간선과 정점 j에서 정점 i로 가는 간선이 같은 간선을 의미하게 된다.
따라서 A[i][j]=A[j][i] 라는 식이 세워지게 된다. 즉 matrix 상으로 봤을 때 대칭구조를 가지고 있다는 것이다.
조금 더 예시를 들어서 설명해보자면,
.png)
위와 같은 그래프가 있다고 해보자. 그렇다면 정점이 5개 이므로 5*5의 배열을 사용하면 되고 간선이 (1,2), (1,3), (2,3), (2,4), (2,5), (3,4), (4,5) 사이에 존재하는 것이라고 할 수 있다.
따라서 해당 칸의 행렬을 생각해보면,
.png)
위와 같이 만들 수 있다. x축은 node i를 나타내고 y축은 node j를 나타내며, i와 j가 연결되어 있다면 1, 아니면 0으로 표현이 된다고 할 수 있다. 양방향 그래프의 경우 (i, j)나 (j, i)가 같기 때문에 해당 표에서도 주황색으로 표시된 대각선 칸을 기준으로 대각선 대칭을 이루는 것을 알 수 있다.
시간복잡도와 공간복잡도는 어떻게 될까?
우선 공간복잡도의 경우에는 V*V 만큼이 필요하다는 것을 알 수 있다 (정점의 개수를 V라고 했을때). 2차원 배열이 필요하기 때문이다.
그렇다면 한 정점과 연결된 모든 간선을 파악하는데 걸리는 시간복잡도는 얼마일까?
이것은 O(V)라고 할 수 있다. 왜냐하면 만약 node 3과 연결된 간선을 파악하기 위해서는
.png)
빨간색으로 표시된 것처럼 node 1부터 node 5까지 V를 검사해주어야 하기 때문이다.
2) 인접 리스트(Adjacency-list)
인접리스트는 리스트를 이용해서 그래프를 구현하는 방식이다.
A[i]= i와 연결된 정점을 리스트로 포함하고 있는 것을 나타낸다고 할 수 있다.
따라서 위의 그래프를 동일하게 적용시킨다면, 인접리스트의 경우
A[1]: 2, 3
A[2]: 1, 3, 4, 5
A[3]: 1, 2, 4
A[4]: 2, 3, 5
A[5]: 2, 4
이런 식으로 표현할 수 있는 것이다.
그렇다면, 인접리스트의 공간복잡도와 시간복잡도는 얼마일까?
우선 간선의 길이를 E라고 했을 때 인접리스트의 공간복잡도는 O(E)이다. 간선이 있는 경우에만 저장을 하기 때문이다.
한 정점과 연결된 모든 간선을 찾는데 걸리는 시간복잡도는 O(차수)라고 할 수 있다.
여기서 차수란 정점과 연결되어 있는 간선의 개수를 의미한다.
인접리스트의 경우 한 정점에 해당하는 배열에 연결되어 있는 간선을 저장해놓기 때문이다.
3) 인접항렬와 인접리스트의 비교
위의 공간복잡도와 시간복잡도에서 알 수 있었듯, 대부분의 경우 인접리스트가 인접항렬을 사용한 것보다 효과적인 모습을 보인다. 따라서 알고리즘을 풀 때, 인접리스트를 사용하는 경우가 많다고 한다.
그러면 인접항렬을 사용하기 좋을 때는 언제일짜?
바로 i와 j node를 이어주는 간선이 있는지 없는지의 유무를 판단할때이다.
해당 경우에 인접항렬을 쓰면 A[i][j]의 값을 검사하기 때문에 O(1)의 시간복잡도를 보이기 때문이다. 반면 인접리스트를 사용하게 되면 앞에서도 언급했지만 O(차수)만큼의 시간복잡도가 걸리기 때문에 인접항렬보다 느리게 된다.
하지만 특수경우을 제외하고는 알고리즘을 푸는 일반적인 경우라면 인접리스트를 쓰는 것을 더 추천하는 바이다.
4) 간선리스트
오늘 소개했던 두 가지 방법이외에도 간선리스트라는 방법이 존재한다. 간선리스트는 말 그대로 간선을 저장하고 있는 경우인데, 매우 특수한 방법이니 우선 위 두 가지 방법만 알아두어도 충분할 것 같다.