Chapter 14. 그래프의 이해와 종류

주의 사항!

• 이 글은 제가 직접 공부하는 중에 작성되고 있습니다.
• 따라서 제가 이해하는 그대로의 내용이 포함됩니다.
• 따라서 이 글은 사실과는 다른 내용이 포함될 수 있습니다.

어플을 사용하면 버스와 지하철의 노선도를 확인할 수 있습니다. 그리고 출발지와 목적지를 입력하면, 그에 맞는 최적의 경로를 알 수도 있습니다. 이러한 프로그램의 구현에 사용되는 것이 바로 그래프 알고리즘입니다. 그래프 알고리즘은 수학자 '오일러'에 의해 고안되었습니다. 오일러는 1736년도에 그 유명한 '쾨니히스베르크의 다리 문제'를 풀기 위해서 그래프 이론을 사용했다고 합니다. 쾨니히스베르크의 다리 문제에 대해 조금 찾아보면 흥미로울 것입니다.

 

다음 그림은 어느 초등학교 5학년 3반 학생들의 비상연락망 구조를 표현한 것입니다.

위 그림에서 학생들의 이니셜이 적힌 점은 '정점'이라고 하고, 이를 연결하는 선은 '간선'이라고 합니다. 그리고 위와 같이 비상 연락망의 구조를 정점과 간선으로 표현한 것을 그래프라고 합니다.

 

위의 그래프에는 방향성이 빠져 있습니다. 따라서 처음 M이 연락을 받았다면, M은 L과 N에게 연락할 것이고, K는 L과 N에게 동시에 연락을 받을 수 있습니다. 이는 다소 비효율적인 방법처럼 보이지만, 대신에 중간에 연락이 끊겨서 다수의 사람이 연락을 받지 못할 확률은 매우 낮아집니다. 이렇듯 방향성이 없는 그래프를 가리켜 '무방향 그래프'라고 합니다.

 

이번에는 그래프에 방향성을 부여해 보겠습니다.

이번에는 M이 연락을 받으면 L에게 연락할 것이고 K는 L에게서만 연락을 받게 될 것입니다. 이렇게 간선에 방향 정보가 포함된 그래프를 가리켜 '방향 그래프' 또는 '다이 그래프'라고 합니다.

 

그래프는 간선의 연결 형태에 따라서 '완전 그래프'로 구분할 수도 있습니다. 완전 그래프란 각각의 정점에서 모든 정점을 연결한 그래프를 뜻합니다. 아래는 완전 그래프의 예입니다.

정점의 수가 동일한 완전 그래프라고 하더라도, 방향 그래프의 간선의 개수는 무방향 그래프의 간선의 수의 두 배가 됩니다.

---

다음 그림에서 보이듯이 간선에 가중치 정보를 두어서 그래프를 구성할 수도 있습니다. 그리고 이러한 유형의 그래프를 가리켜 '가중치 그래프'라고 합니다.

가중치는 두 정점 사이의 거리라든가 두 정점을 이동하는데 걸리는 시간과 같은 정보가 될 수 있습니다. 예를 들어서 위 그래프에서 L에서 N으로 가는 가장 빠른 길을 찾는다면, 그리고 가중치가 이동에 걸리는 시간을 의미한다면 그 결과는 다음과 같습니다. 

 

L → K → N

 

그리고 '부분 집합'과 유사한 개념으로 '부분 그래프'라는 것이 있습니다. 부분 집합이 원래 집합의 일부 원소로 이루어진 집합인 것처럼, 부분 그래프는 원래 그래프의 일부 정점 및 간선으로 이뤄진 그래프를 뜻합니다. 위 그래프의 부분 그래프의 예는 다음과 같습니다.

---

그래프는 정점과 간선의 집합입니다. 따라서 집합의 표기법을 이용해서 표현할 수 있습니다. 먼저, 다음과 같은 무방향 그래프를 집합의 표기법으로 표현해 보겠습니다.

그래프는 정점과 간선으로 이루어지므로, 정점의 집합과 간선의 집합으로 나누어서 표현합니다. 그래프 G에 대한 정점의 집합은 V(G)로 표시하고, 간선의 집합은 E(G)로 표시합니다. 그리고 무방향 그래프에서 정점 A와 정점 B를 연결하는 간선을 (A, B)로 표시합니다. 따라서 위 그래프를 집합으로 표현하면 다음과 같습니다.

무방향 그래프의 간선에는 방향성이 없기 때문에, (K, L)과 (L, K)는 같습니다.

 

이어서 방향 그래프의 집합 표현을 보겠습니다. 방향 그래프의 간선은 방향성이 있기 때문에, 간선의 표현 방법이 무방향 그래프와는 다릅니다. 방향 그래프에서는 A에서 B로 향하는 간선을 <A, B>로 표시합니다. 그래서 다음과 같은 방향 그래프를,

다음과 같이 집합으로 표현할 수 있습니다.

---

이제 그래프를 구현해 보겠습니다. 그래프의 구현을 위해 우선은 그래프의 ADT를 정의해야 합니다. 그래프의 완성형 ADT는 다음과 같은 기능을 가집니다.

 

"그래프를 생성 및 초기화할 때 간선의 방향성 여부를 선택할 수 있고, 가중치의 부여 여부도 선택할 수 있다. 뿐만 아니라, 이후에는 얼마든지 그리고 언제든지 정점과 간선을 삽입하고 삭제할 수 있다." 

 

하지만 지금은 그래프의 구성이 실질적인 목표는 아니기 때문에 그래프의 ADT는 다음과 같이 필요한 만큼만 정의하도록 합니다.

void GraphInit(UALGraph* pg, int nv);
//그래프의 초기화를 진행한다.
//두 번째 인자로 정점의 수를 전달한다.

void GraphDestroy(UALGraph* pg);
//그래프 초기화 과정에서 할당한 리소스를 반환한다.

void AddEdge(UALGraph* pg, int fromV, int toV);
//매개변수 fromV와 toV로 전달된 정점을 연결하는 간선을 그래프에 추가한다.

void ShowGraphEdgeInfo(UALGraph* pg);
//그래프의 간선 정보를 출력한다.

위의 ADT를 보면, 우선 그래프의 초기화 과정에서 정점의 수를 결정하도록 정의하였습니다. 뿐만 아니라 간선을 추가는 하되 삭제는 불가능하도록 정의했습니다. 하지만 이 정도로도 그래프의 구성 이후의 주제를 논의하기에는 충분합니다.

 

정점에 이름을 부여하는 방식은 열거형을 사용할 것입니다. 그래프의 헤더 파일에 다음과 같은 열거형 상수를 선언할 것입니다.

enum {A, B, C, D, E, F, G, H, I, J, K};

이는 정점의 이름을 상수화 한 것입니다. 따라서 GraphInit 함수의 두 번째 인자로 5가 전달되면 5개의 정점을 생성하고, 이들의 이름은 A, B, C, D, E가 될 것입니다.

---

그래프를 구현하는 방법도 배열을 이용하는 방법과 연결 리스트를 이용하는 방법으로 나뉩니다. 하지만 그래프에서는 이들을 각각 '인접 행렬 기반 그래프'와 '인접 리스트 기반 그래프'라고 부릅니다.

 

먼저 인접 행렬 기반 그래프에 대해서 설명하겠습니다. 인접 행렬 기반 그래프는 정방 행렬을 이용해서 구현합니다. 정방 행렬은 행과 열의 개수가 같은 행렬을 말합니다. 따라서 우리는 2차원 배열로 이를 구현하게 됩니다. 다음과 같은 그래프가 있을 때,

이를 인접 행렬 기반 그래프로 표현하면 다음과 같이 됩니다.

위 행렬을 작성하는 방법은 다음과 같습니다. 정점 m과 정점 n이 간선으로 연결되어 있으면 행렬의 m행 n열의 값은 1이 되고, 간선으로 연결되어 있지 않으면 0이 됩니다. 위 그래프는 무방향 그래프이기 때문에, (K, K) 요소로부터 (N, N) 요소로 향하는 대각선을 기준으로 대칭을 이루는 모습입니다.

 

만약 그래프가 다음과 같이 방향 그래프라면,

인접 행렬 기반 그래프는 다음과 같이 표현됩니다.

방향 그래프에 대해서는, 정점 m으로부터 정점 n으로 향하는 간선이 존재할 경우 m행 n열은 1, 간선이 존재하지 않으면 0입니다. 따라서 방향 그래프의 행렬은 대각선을 기준으로 대칭을 이루지 않을 수도 있습니다.

 

이번에는 인접 리스트를 기반의 그래프 표현 방법에 대해 설명하겠습니다. 다음의 무방향 그래프가 있을 때,

인접 리스트 기반의 그래프는 다음과 같이 표현됩니다.

다음과 같은 방향 그래프에 대해서는,

다음과 같이 표현됩니다.