Chapter 10 그래프
1. 그래프란?
① 그래프의 소개
그래프(graph)는 객체 사이의 연결 관계를 표현할 수 있는 자료구조다. 그래프의 대표적인 예는 지도이다. 지하철 노선도는 여러 개의 역들이 어떻게 연결었는지를 보여준다. 지도를 그래프로 표현하면 지하철의 특정한 역에서 다른 역으로 가는 최단 경로를 쉽게 프로그래밍해서 찾을 수 있다.
또한 전기 소자를 그래프로 표현하게 되면 전기 회로의 소자들이 어떻게 연결되어 있는지를 표현해야 회로가 제대로 동작하는지 분석할 수 있으며, 운영체제에서는 프로세스와 자원들이 어떻게 연관되는지를 그래프로 분석하여 시스템의 효율이나 교착상태 유무 등을 알아낼 수 있다.
이러한 많은 문제들은 공통적으로 도시, 소자, 자원, 프로젝트 등의 객체들이 서로 연결되어 있는 구조로 표현 가능하다. 그래프는 이러한 많은 문제들을 표현할 수 있는 훌륭한 논리적 도구라고 볼 수 있다.
우리가 여태까지 배워온 선형리스트나 트리의 구조로는 위와 같은 복잡한 문제들을 표현할 수 없다. 그래프 구조는 인접 행렬이나 인접 리스트로 메모리에 표현되고 처리될 수 있으므로 광범위한 분야의 다양한 문제들을 그래프로 표현하여 컴퓨터 프로그래밍에 의해 해결할 수 있다.
그래프는 아주 일반적인 자료구조로서 앞에서 배웠던 트리도 그래프의 일종이다. 그래프 이론(Graph Theory)은 컴퓨터 학문 분야의 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재한다.
② 그래프의 역사
1736년에 수학자 오일러(Euler)는 "Konigsberg의 다리" 문제를 해결하기 위해 그래프를 최초로 사용하였다. Konigsberg시의 한 가운데에는 Pregel 강이 흐르고 있고 여기에는 7개의 다리가 있다.
Konigsberg Bridge Problem은 "임의의 지역에서 출발하여 모든 다리를 단 한번만 건너서 처음 출발했던 지역으로 돌아올 수 있는가"에 대해 다룬다.
많은 사람들이 이 문제의 답을 찾기 위해 노력했다. 한번 시도해보면 알 수 있다. 그런 방법은 없다는 것이 정답이다. 오일러는 어떤 한 지역에서 시작하여 모든 다리를 한 번씩만 지나서 처음 출발점으로 되돌아오려면 각 지역에 연결된 다리의 개수가 모두 짝수이어야함을 증명하였다. 오일러는 이 문제를 b) 와 같이 간단하게 변경하였다.
③ 그래프로 표현할 수 있는 것들
⑴ 도로
그래프를 통해 도로의 교차점과 일방통행길 등을 효과적으로 표현 가능하다.
⑵ 미로
미로 또한 그래프를 이용해서 효과적으로 표현 가능하다.
⑶ 선수과목 (위상 정렬)
대학교에서 전공과목을 수강하기 위해 미리 들어야 하는 선수과목들이 있다. 그래프는 이러한 선수과목 관계를 적절하게 표현할 수 있다.
2. 그래프의 정의와 용어
① 그래프의 정의
그래프는 정점(vertex)와 간선(edge)들의 유한집합이라 할 수 있다. 수학적으로는 G = (V, E)와 같이 표기한다. 여기서 V(G)는 그래프의 G의 정점들의 집합을 의미하며, E(G)는 그래프 G의 간선들의 집합을 의미한다.
정점: 여러가지 특성을 가질 수 있는 객체 (=Node)
간선: 정점들 간의 관계 (=Link)
그래프는 다음과 같이 집합의 형태로 표현할 수 있다.
V(G1) = { 0, 1, 2, 3 }
E(G1) = { (0, 1), (0, 2), (0, 3), (1, 2) }
② 무방향 그래프와 방향 그래프
간선의 종류에 따라 그래프는 무방향 그래프와 방향 그래프로 구분된다.
무방향 그래프(Undirected Graph): 간선을 통해 양방향으로 갈 수 있음을 나타낸다. 간선 (A, B) = (B, A)
방향 그래프(Directed Graph): 간선에 방향성이 존재하는 그래프로, 도로의 일방통행길과 같다. 간선을 통해서 한쪽 방향으로만 갈 수 있음을 나타낸다. 따라서 정점 A에서 B로만 갈 수 있는 간선은 <A, B>로 표시한다. 간선 <A, B> ≠ <B, A>
V(G1) = { 0, 1, 2, 3 }
E(G1) = { (0, 1), (0, 3), (1, 3), (2, 3) }
V(G2) = { 0, 1, 2, 3 }
E(G2) = { <0, 1>, <0, 3>, <3, 1>, <2, 3> }
③ 네트워크
간선에 가중치를 할당하게 되면, 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연결 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있게 된다. 이렇게 간선에 비용이나 가중치가 할당된 그래프를 가중치 그래프(Weighted Graph) 또는 네트워크(Network)라 일컫는다. 네트워크는 도시와 도시를 연결하는 도로의 길이, 회로 소자의 용량, 통신망의 사용로 등을 추가로 표현할 수 있으므로 그 응용 분야가 보다 광범위하다.
④ 부분 그래프
어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분 그래프(Subgraph)라 부른다. 그래프 G의 부분 그래프 S는 다음과 같은 수식을 만족시킨다.
V(S) ⊆ V(G)
E(S) ⊆ E(G)
⑤ 정점의 차수
그래프에서 인접 정점(Adjacent Vertex)란 간선에 의해 직접 연결된 정점을 뜻한다. 무방향 그래프에서 정점의 차수(degree)는 그 정점에 인접한 정점의 수를 의미한다. 따라서 다음 그림 속 정점 0의 차수는 3이다.
무방향 그래프에서 모든 정점의 차수를 합하면 간선의 수의 2배가 된다. 하나의 간선이 두 개의 정점에 인접하기 때문이다. 위의 그래프에서 모든 정점의 차수의 합은 10이고 간선의 개수는 5이다.
방향 그래프에서는 외부에서 오는 간선의 개수를 진입 차수(in-degree)라 하고 외부로 향하는 간선의 개수를 진출 차수(out-degree)라 한다.
⑥ 경로
무방향 그래프에서 정점 s로부터 정점 e까지의 경로는 정점의 나열 s, v1, v2, ... vk, e로서, 나열된 정점들 간에는 반드시 간선 <s, v1>, <v1, v2>, ..., <vk, e>가 있어야 한다. 그래프에서 0, 1, 2, 3은 경로지만 0, 1, 3, 2는 경로가 아니다. 왜냐하면 간선 (1, 3)이 존재하지 않기 때문이다.
경로 중에서 반복되는 간선이 없을 경우에 이러한 경로를 단순 경로(Simple Path)라 한다. 만약에 단순 경로의 시작 정점과 종료 정점이 동일하다면 이러한 경로를 사이클(Cycle)이라 한다.
⑦ 연결 그래프
무방향 그래프 G에 있는 모든 정점쌍에 대하여 항상 경로가 존재할 경우 G는 연결되었다고 한다. 이러한 무방향 그래프 G를 연결 그래프(Connected Graph)라 부른다. 그렇지 않은 그래프는 비연결 그래프(Unconnected Graph)라고 한다.
+ 트리는 사이클을 가지지 않는 연결 그래프를 말한다.
⑧ 완전 그래프
그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프(Complete Graph)라고 한다. 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결된다. 따라서 간선의 수는 n x (n-1) / 2가 된다.
완전 그래프 n = 4 일 때, 간선의 수 = (4 x 3) / 2 = 6
3. 그래프의 표현 방법
그래프를 표현하는 방법에는 다음과 같이 2가지의 방법이 있다. 그래프 문제의 특성에 따라 다음의 두 가지 표현 방법은 각각 메모리 사용량과 처리 시간 등에서 장단점을 가지므로, 문제에 적합한 표현 방법을 선택해야 한다.
① 인접 행렬
그래프의 정점 수가 n일 때, n x n의 2차원 배열인 인접 행렬(Adjacency Matrix) M을 이용해서 메모리에 표현할 수 있다. 인접 행렬 M의 각 원소는 다음 규칙을 따라 메모리에 할당된다.
if (간선 (i, j)가 그래프에 존재) M[i][j] = 1,
otherwise M[i][j] = 0.
우리가 다루고 있는 그래프에서는 자체 간선을 허용하지 않으므로 인접 행렬의 대각선 성분은 모두 0으로 표현된다. 무방향 그래프의 인접 행렬은 대칭 행렬이 된다. 이는 무방향 그래프의 간선 (i, j)는 정점 i에서 정점 j로의 연결뿐만 아니라 정점 j에서 정점 i로의 연결을 동시에 의미하기 때문이다. 그 결과, 무방향 그래프에서 배열의 상위 삼각, 하위 삼각만 저장하면 메모리를 절약할 수 있다.
n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 무관하게 항상 n^2개의 메모리 공간이 필요하다. 이에 따라 인접 행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(Dense Graph)를 표현하는 경우에 적합하다. 반면에, 적은 숫자의 간선만을 가지는 희소 그래프에는 메모리 낭비가 크므로 적합하지 않다.
인접 행렬을 이용하면 두 정점을 연결하는 간선의 존재 여부를 O(1)시간 안에 즉시 알 수 있는 장점이 있다. 즉 정점 u와 정점 v를 연결하는 정점이 있는지를 알려면 M[u][v]의 값을 조사하면 바로 알 수 있다.
또한 정점의 차수는 인접 행렬의 행이나 열을 조사하면 알 수 있으므로 O(n)의 연산이 필요하다.
정점 i에 대한 차수는 다음과 같이 인접 배열의 i번째 행에 있는 값을 모두 더하면 된다.
반면에 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 n^2번의 조사가 필요하게 되어 O(n^2)의 시간이 요구된다.
② 인접 행렬을 이용한 그래프 ADT 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat [MAX_VERTICES] [MAX_VERTICES];
} GraphType;
// 그래프 초기화
void init(GraphType* g)
{
int r, c; g->n = 0;
for (r = 0; r<MAX_VERTICES; r++)
for (c = 0; c<MAX_VERTICES; c++)
g->adj_mat[r][c] = 0;
}
// 정점 삽입 연산
void insert_vertex (GraphType* g, int v)
{
if (((g->n) + 1) > MAX_VERTICES) {
fprintf(stderr, "그래프: 정점의 개수 초과");
return;
}
g->n++;
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end)
{
if (start >= g->n || end >= g->n) {
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
g->adj_mat[start] [end] = 1;
g->adj_mat[end] [start] = 1;
}
// 인접 행렬 출력 함수
void print_adj_mat (GraphType* g)
{
for (int i = 0; i < g->n; i++) {
for (int j = 0; j < g->n; j++) {
printf("%d ", g->adj_mat[i][j]);
}
printf("\n");
}
}
void main()
{
GraphType *g;
g= (GraphType *)malloc(sizeof(GraphType));
init(g);
for (int i=0;i<4;i++)
insert_vertex(g, i);
insert_edge(g, 0, 1);
insert_edge(g, 0, 2);
insert_edge(g, 0, 3);
insert_edge(g, 1, 2);
insert_edge(g, 2, 3);
print_adj_mat (g);
free(g);
}
[실행결과]
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0
③ 인접 리스트
인접 리스트(Adjacency List)는 그래프를 표현함에 있어 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것이다. 각 연결 리스트의 노드들은 인접 정점을 저장하게 된다. 각 연결 리스트들은 헤더 노드를 가지고 있고 이 헤더 노드들은 하나의 배열로 구성되어 있다. 따라서 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수 있다.
무방향 그래프의 경우 정점 i와 정점 j를 연결하는 간선 (i, j)는 정점 i의 연결 리스트에 인접 정점 j로서 한번 표현되고, 정점 j의 연결 리스트에 인접 정점 i로 다시 한번 표기된다. 인접 리스트의 각각의 연결 리스트에 정점들이 입력되는 순서에 따라 연결 리스트 내에서 정점들의 순서가 달라질 수 있다. 다음 그림은 정점의 오름차순으로 연결한 인접 리스트 그림이다.
정점의 수가 n개인 무방향 그래프를 표시하기 위해서는 n개의 연결 리스트가 필요하다. 이외 관계는 다음과 같다.
| 정점의 수 | 간선의 수 | |
| 무방향 그래프 | n | e |
| 인접 리스트 | n개의 헤더 노드 | 2e개의 노드 |
인접 행렬 표현은 간선의 개수가 적은 희소 그래프(Sparse Graph)의 표현에 적합하다.
그래프에서 간선(i, j)의 존재 여부와 정점 i의 차수를 알기 위해서는 인접 리스트의 정점 i의 연결 리스트를 탐색해야 한다. 따라서 연결 리스트에 있는 노드의 수만큼, 즉 정점 차수만큼의 시간이 필요하다.
즉, n개의 정점과 e개의 간선을 가진 그래프에서 전체 간선의 수를 알아내려면
헤더 노드를 포함하여 모든 인접 리스트를 조사해야 하므로 O(n + e)의 연산이 요구된다.
④ 인접 리스트를 이용한 그래프 ADT 구현
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTICES 50
typedef struct GraphNode
{
int vertex;
struct GraphNode* link;
} GraphNode;
typedef struct GraphType {
int n; // 정점의 개수
GraphNode* adj_list[MAX_VERTICES];
} GraphType;
// 그래프 초기화
void init(GraphType* g)
{
int v;
g->n = 0;
for (v=0; v < MAX_VERTICES; v++)
g->adj_list[v] = NULL;
}
// 정점 삽입 연산
void insert_vertex(GraphType* g, int v)
{
if (((g->n)+1)>MAX_VERTICES) {
fprintf(stderr, "그래프: 정점의 개수 초과");
return;
}
g->n++;
}
// 간선 삽입 연산, v를 u의 인접 리스트에 삽입한다.
void insert_edge (GraphType* g, int u, int v)
{
GraphNode* node;
if (u >= g->n || v >= g->n) {
fprintf(stderr, "그래프: 정점 번호 오류");
return;
}
node = (GraphNode*)malloc(sizeof(GraphNode));
node-> vertex = v;
node->link = g->adj_list[u];
g->adj_list[u] = node;
}
/* 정점 u에 간선 (u, v)를 삽입하는 연산은 정점 u의 인접 리스트에 간선을 나타내는 노드를 하나 생성하여 삽입하면 된다.
위치 는 상관이 없으므로 삽입을 쉽게 하기 위하여 연결 리스트의 맨 처음에 삽입하도록 한다. */
void print_adj_list(GraphType* g)
{
for (int i = 0; i<g->n; i++) {
GraphNode* p = g->adj_list[i];
printf("정점 %d의 인접 리스트 ", i);
while (p!=NULL) {
printf("-> %d ", p->vertex);
p = p->link;
}
printf("\n");
}
}
int main()
{
GraphType *g;
g = (GraphType *)malloc(sizeof(GraphType));
init(g);
for (int i=0;i<4;i++)
insert_vertex(g, i);
insert_edge(g, 0, 1);
insert_edge(g, 1, 0);
insert_edge(g, 0, 2);
insert_edge(g, 2, 0);
insert_edge(g, 0, 3);
insert_edge(g, 3, 0);
insert_edge(g, 1, 2);
insert_edge(g, 2, 1);
insert_edge(g, 2, 3);
insert_edge(g, 3, 2);
print_adj_list(g);
free (g);
return 0;
}
[실행결과]
정점 0의 인접 리스트 -> 3 -> 2 -> 1
정점 1의 인접 리스트 -> 2 -> 0
정점 2의 인접 리스트 -> 3 -> 1 -> 0
정점 3의 인접 리스트 -> 2 -> 0