트리와 그래프의 구현

길 찾기 프로그램을 만들려고 도시의 교차로와 도로를 컴퓨터에 담는다. 교차로 사이가 도로로 이어졌는지를 가로세로 모두 교차로 이름이 붙은 표에 0과 1로 적으면 이해하기 쉽다. 그런데 교차로가 1만 개이면 표는 1억 칸이 되고, 그 칸 대부분은 0이다. 교차로 하나에 이어진 도로는 기껏해야 네댓 개이기 때문이다. 같은 연결 관계를 더 적은 메모리로 담는 방법이 있을까? 그리고 두 방법은 어떤 일에서 각각 빠를까?

정점(교차로)의 수

정점마다 평균 이웃 수

2.3.1그래프와 트리

그래프는 정점(점)과 그 사이를 잇는 간선(선)으로 '무엇이 무엇과 이어져 있는가'를 나타내는 자료 구조이다. 지하철역과 노선, 사람과 친구 관계, 웹 문서와 링크가 그래프이다. 간선에 방향이 있으면 방향 그래프, 거리나 시간 같은 값이 붙으면 가중치 그래프이다. 트리는 그래프 가운데 고리가 없고 모든 정점이 이어진 것으로, 맨 위의 뿌리에서 가지가 갈라진다. 폴더 구조, 가계도, 토너먼트 대진표가 트리이다. 정점이 \(n\)개인 트리에는 간선이 늘 \(n - 1\)개 있다.

그림 1에서 두 값을 바꾸어 보자. 교차로 1만 개, 교차로마다 이웃 4개이면 행렬은 1억 칸, 리스트는 약 5만 칸으로 2000배 차이 난다. 정점이 100만 개인 큰 도시라면 행렬은 1조 칸이라 보통 컴퓨터에 담을 수조차 없다. 그런데 이웃 수가 정점 수에 가까운 빽빽한 그래프라면 두 방법의 크기 차이가 줄고, 행렬이 '이웃인가'를 빨리 답하는 장점이 커진다. 그래서 그래프의 모양과 자주 할 연산을 보고 저장 방법을 고른다.¹

2.3.2트리의 구현

트리는 각 정점이 자식들의 목록을 가지게 하여 만든다. 자식이 많아야 둘인 이진 트리는 각 정점이 값, 왼쪽 자식, 오른쪽 자식을 가지게 하거나, 리스트 하나에 1번부터 차례로 담고 \(i\)번 정점의 자식을 \(2i\)번과 \(2i + 1\)번 자리에 두기도 한다. 리스트로 담는 방식은 트리가 고르게 채워져 있을 때 메모리를 아끼고, 부모와 자식을 계산만으로 찾을 수 있다. 하지만 트리가 한쪽으로 치우치면 빈자리가 많아진다. 그래프와 마찬가지로 트리도 모양에 따라 알맞은 구현이 다르다.

2.3.3예제 풀이

인접 행렬은 5 × 5 = 25칸이고, A–B, A–C, B–D, C–D, D–E에 해당하는 칸이 양쪽으로 1이라 1이 10칸, 0이 15칸이다. 인접 리스트는 A: [B, C], B: [A, D], C: [A, D], D: [B, C, E], E: [D]로, 정점 5칸과 이웃 10칸을 합쳐 15칸이다.

이 그래프는 정점 5개에 간선 5개로, 트리의 간선 수 4보다 하나 많아 고리가 하나 있다. 고리는 A–B–D–C–A이다. 이 고리에 속한 A–B, B–D, C–D, A–C 가운데 하나를 지우면 트리가 된다. D–E를 지우면 E가 떨어져 나가므로 안 된다. 즉 자료 구조를 고르는 일은 연결 관계의 모양을 이해하는 일에서 시작한다. 그래서 정점과 간선의 수, 고리가 있는지를 먼저 살펴 그래프인지 트리인지, 어떤 저장 방법이 알맞은지 정한다.

아래 탐구 카드에서 지하철 노선도와 폴더 구조를 그래프와 트리로 담아 보고, 두 저장 방법을 비교해 보자.

1. 1736년 오일러는 쾨니히스베르크의 다리 일곱 개를 한 번씩만 건너는 길이 없음을 보이며, 땅을 점으로, 다리를 선으로 바꾸어 생각했다. 이것이 그래프 이론의 시작으로 꼽힌다.