인접 행렬
인접 리스트

1. 인접 행렬 (adjacency matrix)

01. 정의

이름에서 유추할 수 있듯이 |V| x |V| 크기의 행렬, 즉 2차원 배열을 이용해 그래프의 간선정보를 저장한 것이다.

02. 특징

[단점] n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수에 무관하게 항상 n^2개의 메모리 공간이 필요하다.
따라서 그래프에 간선이 많이 존재하는 밀집 그래프를 표현하는 경우에 적합하나, 그래프 내에 적은 숫자의 간선만을 가지는 희소 그래프의 경우에는 메모리의 낭비가 크므로 적합하지 않다.
[장점] 두 정점을 연결하는 간선의 존재 여부를 O(1) 시간 안에 즉시 알 수 있다. 즉, 정점 u와 정점 v를 연결하는 정점이 있는지를 알려면 M[u][v]의 값을 조사하면 된다.
[장점] 또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 O(n)의 연산으로 알 수 있다.

03. 구현

ExampleGraph

정점 : [1, 2, 3, 4, 5, 6]
간선 : [[1, 2], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]]

// 무방향 그래프인 경우를 다룹니다.

const v = [1, 2, 3, 4, 5];
const e = [
	[1, 2],
	[1, 5],
	[2, 3],
	[2, 4],
	[2, 5],
	[3, 4],
	[4, 5],
];

// 편의를 위해 1 증가
const matrix = Array.from({length: v.length + 1}, () =>
	Array(v.length + 1).fill(0)
);

for (let i = 0; i < e.length; i++) {
	matrix[e[i][0]][e[i][1]] = matrix[e[i][1]][e[i][0]] = 1;
}

console.log(matrix);

// 출력
[
	[0, 0, 0, 0, 0, 0],
	[0, 0, 1, 0, 0, 1],
	[0, 1, 0, 1, 1, 1],
	[0, 0, 1, 0, 1, 0],
	[0, 0, 1, 1, 0, 1],
	[0, 1, 1, 0, 1, 0],
];

2. 인접 리스트 (adjacency list)

01. 정의

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록을 저장해서 표현한 것이다.
따라서 그래프는 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현된다.

02. 특징

정점의 수가 v 개이고, 간선의 수가 e개인 무방향 그래프를 표시하기 위해서는 n 개의 연결 리스트가 필요하고, n 개의 헤더 노드와 2e개의 노드가 필요하다.
[단점] 간 선 (i, j)의 존재 여부나 정점 i의 차수를 알기 위해서는 정점 i의 연결 리스트에 있는 노드의 수만큼 탐색을 해야 한다. 즉 정점 차수 만큼의 시간이 필요하다.

03. 구현

ExampleGraph

정점 : [1, 2, 3, 4, 5, 6]
간선 : [[1, 2], [1, 5], [2, 3], [2, 4], [2, 5], [3, 4], [4, 5]]

// 무방향 그래프인 경우를 다룹니다.

const v = [1, 2, 3, 4, 5];
const e = [
	[1, 2],
	[1, 5],
	[2, 3],
	[2, 4],
	[2, 5],
	[3, 4],
	[4, 5],
];

// 편의를 위해 1 증가
const list = Array.from({length: v.length + 1}, () => []);

for (let i = 0; i < e.length; i++) {
	const from = e[i][0];
	const to = e[i][1];

	list[from].push(to);
	list[to].push(from);
}

console.log(list);

// 출력
[[], [2, 5], [1, 5, 3, 4], [2, 4], [3, 2, 5], [1, 2, 4]];

3. 인접 행렬과 인접 리스트 비교

한 방식의 단점이 바로 다른 방식의 장점이기 때문에 구현하려는 알고리즘의 종류나 그래프의 종류에 따라 적절히 선택해 사용해야 한다.
인접 행렬 표현의 가장 큰 장점은 정점의 번호 u, v가 주어졌을 때, 두 정점을 잇는 간선의 존재 여부를 한 번의 배열 접근만으로 확인할 수 있다는 것이다. 인접 리스트 표현의 경우, 간선 (u, v)의 존재 여부를 확인하기 위해 연결리스트를 처음부터 읽어가며 일일이 확인해야 한다.
반면, 인접 행렬 표현은 |V| x |V| 크기의 2차원 배열을 사용하기 때문에 간선의 개수와 관계없이 항상 O(|V|^2) 크기의 공간을 사용한다는 문제점이 있다. 인접 리스트 표현은 |V|개의 연결 리스트에 실제 간선 수만큼의 원소가 들어 있으므로 O(|V| + |E|)의 공간만 사용한다.
따라서 희소 그래프에 대해서는 인접 리스트를, 밀집 그래프에 대해서는 인접 행렬을 사용하는 것이 더 유리하다.

3.0. 참고 지식

희소 그래프 : 간선의 수가 |V|^2에 비해 훨씬 적은 그래프
밀집 그래프 : 간선의 수가 거의 |V|^2에 비례하는 그래프

4. 출처

C언어로 쉽게 풀어쓴 자료구조 (천인국, 공용해, 하상호)
프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 (구종만)