그래프는 비선형 자료구조의 하나로서 정점(노드)과 간선(엣지)으로 이루어진 구조입니다. 정점들 간에는 서로를 이어주는 간선이 있을 수도 있고 없을 수도 있습니다. 그래프 상에 존재하는 각 두 정점들 간의 관계(간선이 있는지 없는지)를 구조화해서 나타 낼 수 있는데, 이를 인접 행렬과 인접 리스트라고 칭합니다. 그래프의 간선은 방향을 가질 수 있지만 이 글에서는 방향이 없는 간선을 가진 그래프를 기준으로 인접 행렬과 리스트를 다루겠습니다.
인접 행렬 (Adjacency Matrix)
인접 행렬은 2차원 배열로서 노드 갯수 * 노드갯수 만큼의 크기를 가지며 즉, N * N 배열이라고 생각하시면 됩니다. 이 2차원 배열을 adjs라 하고 adjs[i][j] 를 통해서 해당 값에 접근을 하면 이 값은 노드 i 에서 j 로 가는 간선의 유무를 나타냅니다. 노드간에 간선이 있다는 것을 1로 표현 한다면 adjs[i][j] === 1 가 참일경우 i 와 j가 이어져 있다는 것을 의미합니다. 그리고 간선에 방향이 없으므로 j에서 i로 가는 간선도 마찬가지로 존재하는 것이니까 adjs[j][i] = 1 이 됩니다. 만약 값이 0일 경우에는 일반적으로 노드들이 이어져 있지 않다고 간주합니다.
인접행렬은 가중치를 가진 그래프를 표현하는 데도 쓰입니다. 만약 adjs[i][j] = w 라면 i 에서 j로 가는 가중치는 w가 됩니다. 가중치를 따로 두지 않았을 경우에는 보통 1로 여기게 됩니다.
0 ~ 4까지의 노드를 가진 무방향 그래프를 한번 그려본다면,
이 그래프를 토대로 인접 행렬을 통해 노드 간의 관계를 나타내어 본다면 다음과 같습니다.
인접 행렬을 보시면 0은 1과 4와 연결 되어 있으니 각각 표에서 1이라는 값을 가집니다. 위 인접행렬을 2차원 배열로는
[[0, 1, 0, 0, 1], [1, 0, 1, 0, 0], [0, 1, 0, 1, 0], [0, 0, 1, 0, 1], [1, 0, 0, 1, 0]] 와 같이 나타내면 됩니다.
만약 가중치가 있는 그래프를 나타내면 각 간선에 가중치가 생겨 인접 행렬에 변화가 생깁니다.
인접 리스트 (Adjacency List)
인접 리스트는 연결리스트(Linked List)의 배열로 나타냅니다. 배열의 각 요소는 연결 리스트이고 리스트 각각의 첫 노드는 한 정점을 나타냅니다. 이 노드에 연결된 나머지 리스트는 이 정점에 이어진 정점들을 의미합니다. 연결리스트를 조금 더 활용하여 가중치 값을 포함하게 해준다면 인접리스트로도 가중치 있는 그래프를 표현할 수도 있습니다.
사실 자바스크립트에서는 연결리스트를 보통 배열이나 객체 같은 참조값으로 표현합니다. 따라서 연결 리스트를 배열로 생각하고 표현하면 인접리스트는 배열의 배열(?) 이라고 생각하시면 될 것 같습니다. 바깥 배열의 각 인덱스는 정점의 번호라 생각하고 그 인덱스에 할당된 배열은 해당 정점에 연결된 정점들이라 할 수 있습니다.
이렇게 말로 하면 머릿속에 잘 그려지지 않을 것 같아서 위 그림 1 그래프를 토대로 인접 리스트를 만들어 봤습니다. 리스트의 배열로 표현이 되고, 배열의 각 인덱스가 각 정점을 나타냅니다.
예를 들어, 정점 1은 정점 0과 2에 연결 되어 있으니 헤드 1에 노드 0과 2가 이어집니다. 헤드는 정점을 의미하고, 각 노드의 Next는 헤드에 연결된 노드를 가리킵니다. 이와 같이 리스트로 표현하기가 어렵다면 배열로 표현해 보겠습니다.
배열로 표현하니 익숙한 그림이 나옵니다. 그림을 보면 인접리스트가 인접행렬보다 좀 더 간단해 보인다고 생각할 수도 있습니다.
각각의 특징을 알고 행렬과 리스트를 골라서 쓰면 될 것 같습니다.
둘을 비교해 본다면,
- 인접 행렬은 이어지지 않은 점 까지 배열에 표현하기 때문에 메모리 공간을 더 많이 쓰게 된다. (N^2)
- 인접 행렬은 정점의 갯수가 많을 경우에는 탐색을 하는데에 시간이 많이 들게된다. (연결 안된 것도 확인하게 됨)
- 대신 구현이 쉽고, 정점 간의 가중치를 표현하는 것도 수월하다.
- 인접리스트는 두 정점간의 관계(연결 여부)를 확인해보기 위해서는 해당 정점에 연결된 정점 리스트 전체를 탐색하게 될 수도 있다.
- 인접행렬은 두 정점간의 관계를 확인할 때 좋은 효율을 가지고,
- 인접리스트는 그래프를 전체적으로 탐색할 때 유리하다.
참고로, 다익스트라 알고리즘에서 인접리스트를 사용하면 편리한데 최단 거리를 갱신해가면서 찾는 알고리즘이기 때문에 가중치가 존재 할 수 있습니다. 여기서는 인접 행렬보다는 인접 리스트를 사용하는 것이 시간적으로 유리하고, 인접 리스트에서 가중치를 포함하여 저장하는 방법은 다음과 같습니다. 그림 2.1의 가중치 그래프를 기준으로 인접리스트를 구성하면,
위와 같이 인접 리스트를 구조화하여 가중치 표현 또한 가능합니다.
틀린 부분이 있다면 과감한 지적 부탁드립니다!
참조
'algorithm > 개념' 카테고리의 다른 글
| 힙 정렬(Heap Sort) (0) | 2021.06.06 |
|---|---|
| 병합 정렬 알고리즘(Merge Sort) (0) | 2021.06.06 |
| 퀵정렬 알고리즘(Quick Sort) (0) | 2021.06.06 |
| 객체지향 프로그래밍이란? (0) | 2021.06.03 |
| 배열과 연결리스트 (0) | 2021.06.01 |
