[코딩테스트/알고리즘] 그래프(Graph) - 그래프의 표현

이번 글에는 그래프를 표현하는 방법에 대해 알아보도록 하겠다.

정점 : {1, 2, 3, 4, 5, 6}
간선 : {(1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (3, 4), (3, 6), (3, 6), (4, 6)}

---

1. 인접 행렬

V개의 정점이 있을 때 V ☓ V 사이즈의 이차원 배열을 통해 나타낸다.

정점 i와 정점 j가 연결되어있을 때

• A[i][j] = 1

정점 i와 정점 j가 연결되어있지 않을 때

• A[i][j] = 0

예시

	1	2	3	4	5	6
1		1	0	0	1	0
2	1		1	0	1	0
3	0	1		1	0	1
4	0	0	1		1	1
5	1	1	0	1		0
6	0	0	1	1	0

---

2. 인접 리스트

리스트(배열)를 이용해서 구현한다. 리스트는 크기를 동적으로 변경할 수 있어야 한다. 때문에 연결 리스트나 길이를 동적으로 변경할 수 있는 배열을 사용한다.
A[i] = i와 연결된 모든 정점을 저장함.

정점	인접한 정점
A[1]	2, 5
A[2]	1, 3, 4, 5
A[3]	2, 4
A[4]	3, 5, 2, 6
A[5]	1, 2, 4
A[6]	4

---

3. 간선 리스트

배열을 이용해서 구현한다. 그래프에 존재하는 간선을 모두 저장하고 있다.
E[1] = 1 2
E[2] = 1 5
E[3] = 2 3
E[4] = 2 4
E[5] = 2 5
E[6] = 5 4
E[7] = 4 3
E[8] = 2 1
E[9] = 5 1
E[10] = 3 2
E[11] = 4 2
E[12] = 5 2
E[13] =4 5
E[14] = 3 4
E[15] = 6 4

---

총평

하려던 일 계속 미루다가 겨우 끝낸 느낌이다.