그래프
- 객체 사이의 연결 관계를 표현할 수 있는 자료구조
> 그래프는 아주 일반적인 자료구조로서 앞에서 다뤘던 트리도 그래프의 하나의 특수한 종료로 볼 수 있다. 그래프이론은 컴퓨터 학문에서 활발한 연구 주제이며 문제 해결을 위한 도구로서 많은 이론과 응용이 존재한다.
- 그래프 정의
> 그래프는 정점(vertex)과 간선(edge)들의 유한 집합니다. 수학적으로 G=(V, E)와 같이 표시한다. 여기서 V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다.
> 정점은 여러가지 특성을 가질 수 있는 객체를 의미하고 간선은 이러한 정점들 간의 관계를 의미한다.
정점(vertex)은 노드(node)라고 불리며, 간선(edge)은 링크(link)라고 불린다
- 그래프의 종류
> 간선의 종류에 따라 그래프는 무방향 그래프와 방향 그래프로 구분된다.
무방향 그래프 (undirected graph)> 간선은 간선을 통해서 양방향으로 갈 수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선은(A, B)와 같이 정점의 쌍으로 표현한다. (A, B), (B, A)는 같은 간선이다
방향 그래프 (directed graph)> 간선에 방향성이 존재하는 그래프로서 도로의 일방통행 처럼 간선을 통해 한쪽 방향으로만 갈 수 있음을 나타낸다. 정점 A에서 정점 B로만 갈 수 있는 단선은 <A, B>로 표시하고, <A, B>, <B, A>는 다른 간선이다
- 네트워크
> 간선에 가중치를 할당하게 되면 간선의 역할이 두 정점간의 연결 유무뿐만 아니라 연걸 강도까지 나타낼 수 있으므로 보다 복잡한 관계를 표현할 수 있다.
> 간선이 비용이나 가중치가 할당된 그래프를 가중치 그래프 또는 네트워크라고 한다.
- 부분 그래프
> 어떤 그래프의 정점의 일부와 간선의 일부로 이루어진 그래프를 부분그래프라고 한다
V(S) ⊆ V(G)
E(S) ⊆ E(G)
- 정점의 차수
> 그래프에서 인접 정점(adjacent vertex)란 간선에 의해 직접 연결된 정점이다. 무방향 그래프에서 정점의 차수는 그 정점에 인접한 정점의 수를 말한다.
> 무방향 그래프에서 모든 정점의 차수를 합하면 간선 수의 2배가 된다. 왜냐하면 하나의 간선이 두 개의 정점에 인접하기 때문이다. 방향 그래프에서는 외부에서 오는 간선의 개수를 진입차수(in degree)라고 하며 외부로 향하는 간선의 개수를 진출 차수(dout degree)라고 한다.
- 경로(path)
> 무방향 그래프에서 정점s로 부터 정점 e까지의 경로는 나열된 정점들 간에 반드시 간선이 존재해야 한다. 경로 중에서 반복되는 간선이 없는 경우 단순경로(simple path)라고 하며 단순 경로의 시작 정점과 종료 정점이 동일하다면 사이클(cycle)이라고 한다.
- 연결 그래프(connected graph)
> 무방향 그래프 G에 있는 모든 정점쌍에 대하여 상항 경로가 존재한다면 G는 연결되었다고 하며 이러한 무방향 그래프 G를 연결 그래프라고 한다. 그렇지 않은 그래프는 비연결그래프(unconnected graph)라고 한다. 트리는 그래프의 특수한 형태로써 사이클을 가지지 않은 연결 그래프이다.
- 완전 그래프( complete graph)
> 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전그래프라고 한다. 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n x (n-1) / 2가 된다.
- 그래프 추상 데이터 타입
create_graph()::=그래프를 생성한다
init(g)::=그래프 g를 초기화한다
insert_vertex(g)::=그래프 g에 정점 v를 삽입한다
insert_edge(g,u,v)::=그래프 g에 간선(u,v)를 삽입한다
delete_vertex(g,v)::=그래프 g에 정점 v를 삭제한다
delete_edge(g,u,v)::=그래프 g에 간선 (u,v)를 삭제한다.
is_empty(g)::=그래프 g가 공백 상태인지 확인한다
adjacent(v)::=정점 v에 인접한 정점들의 리스트를 반환한다
distroy_graph(g)::=그리프 g를 제거한다
그래프 표현방법
- 인접 행렬(adjacency matrix): 2차원 배열을 사용하여 그래프를 표현한다
- 인접 리스트(adjacency list): 연결 리스트를 사용하는 그래프를 표현한다
- 인접 행렬
> 그래프의 정점 수가 n이라면 n x n의 2차원 배열인 인접행렬 M의 각 원소를 다음 규칙에 의해 할당함으로써 그래프를 메모리에 표현할 수 있다.
if (간선(i,j)가 그래프에 존재) M[i][j]=1;
otherwise M[i][j]=0;> 그래프에서는 자체 간선을 허용하지 않으므로 인접 행렬의 대각선 성분은 모두 0으로 표시된다.
> 무방향 그래프의 경우 배열의 상위 삼각이나 하위 삼각만 저장하면 메모리를 절약할 수 있다.
> n개의 정점을 가지는 그래프를 인접 행렬로 표현하기 위해서는 간선의 수와 무관하게 n^2개의 메모리 공간이 필요하다. 따라서 인접행렬은 그래프에 간선이 많이 존재하는 밀집 그래프(dense graph)를 표현하는 경우에 적합하다. 그래프 내에 적은 숫자의 간선만을 가지는 희소그래프(sparse graph)의 경우에는 메모리의 낭비가 크므로 적합하지 않다
> 인접행렬을 이용하면 두 정점을 연결하는 간선의 존재여부를 O(1)시간 안에 즉시 알 수 있다. 정점 u와 v를 연결하는 정점이 있는지 알려면 M [u][v]의 값을 조사하면 바로 알 수 있다.
> 정점의 차수는 인접 행렬의 행이나 열을 조사하면 바로 알 수 있으므로 O(n)의 연산에 의해 알수 있다. 정점 i에 대한 차수는 인접 배열 i번째 행에 있는 값을 모두 더하면 된다.
- 인접행렬 시간복잡도-
> 그래프에 존재하는 모든 간선의 수를 알아내려면 인접 행렬 전체를 조사해야 하므로 n^2번의 조사가 필요하게 되어 O(n^2)의 시간이 요구된다.
- 그래프 추상데이터 타입 구현, 인접행렬을 이용한 -
> 그래프에 관련된 변수들은 하나의 구조체 Graphtype에 정리하는데, 먼저 그래프에 존재하는 정점의 개수 n이 필요하며 인접 행렬을 이용하여 구현되려면 크기가 n x n인 2차원 배열인 인접행렬도 필요하다. 이와 같은 방식으로 구현하면 한정된 개수의 정점까지만 그래프를 삽입할 수 있다. 만약 동적 배열로 구현한다면 정점을 삽입할 때마다 다시 크기를 조장할 수 있다.
#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("%2d ", 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);
}
- 인접 리스트
> 그래프를 표현함에 있어서 각각의 정점에 인접한 정점들을 연결 리스트로 표시한 것. 각 연결 리스트들의 노드들은 인접정점을 저장하게 된다. 연결 리스트들은 헤더 노드를 가지고 있으며 이 헤더 노드들은 하나의 배열로 구성되어 있다. 따라 정점의 번호만 알면 이 번호를 배열의 인덱스로 하여 각 정점의 연결 리스트에 쉽게 접근할 수 있다.
- 그래프 추상 데이터 타입 구현, 인접리스트를 이용한 -
> 그래프에 관련된 변수들을 하나의 구조체 GraphType에 정리하면 먼저 그래프에 존재하는 정점의 개수 n이 필요하다. 인접 리스트를 이용하여 구현하려면 각 정점마다 하나의 연결 리스트가 필요하다. 따라서 정점의 개수만큼의 포인터 배열이 필요하다
#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;
}
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;
}
그래프의 탐색
>그래프의 탐색은 가장 기본적인 연산으로서 하나의 정점으로부터 시작하여 차례대로 모든 점점을 하나씩 방문하는 것이다. 특정한 정점에서 다른 정점으로 갈 수 있을지 없을지 탐색을 통해서 알 수 있다.
- 방식
- 깊이 우선 탐색(DFS: depth first search)
- 너비 우선 탐색(BFS: breath first search)
- 깊이 우선 탐색
- 그래프의 시작 정점에서 출발하여 시작 정점 v를 방문했다고 표시한다
- v에 인접한 정점들 중에서 아직 방문하지 않은 정점 u를 선택한다. 만약 그런 정점이 없으면 종료한다
- 만약 아직 방문하지 않은 정점 u가 있다면 u를 시작 정점으로 하여 깊이 우선 탐색을 다시 시작한다
- 탐색이 긑나게 되면 다시 v에 인접한 정점들 중에서 아직 방문이 안된 정점을 찾는다
- 만약 없으면 종료하고 있다가 다시 그 정점을 시작 정점으로 하여 깊이 우선 탐색을 시작한다.
- 깊이 우선 탐색의 구현, 인접 행렬 사용 -
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
// 그래프 초기화
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 dfs_mat(GraphType* g, int v)
{
int w;
visited[v] = TRUE; // 정점 v의 방문 표시
printf("정점 %d -> ", v); // 방문한 정점 출력
for (w = 0; w<g->n; w++) // 인접 정점 탐색
if (g->adj_mat[v][w] && !visited[w])
dfs_mat(g, w); //정점 w에서 DFS 새로 시작
}
int main(void)
{
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);
printf("깊이 우선 탐색\n");
dfs_mat(g, 0);
printf("\n");
free(g);
return 0;
}
- 깊이 우선 탐색의 구현, 인접 리스트를 이용한 -
> 인접 리스트는 다수의 연결 리스트로 구성되는데, 각 연결 리스트의 노드는 데이터 필드와 링크 필드로 이루어져 있어 데이터 필드에는 인접 정점의 번호가 저장되고 링크 필드에는 다음 인접정점을 가리키는 포인터가 저장된다
int visited[MAX_VERTICES];
// 인접 리스트로 표현된 그래프에 대한 깊이 우선 탐색
void dfs_list(GraphType* g, int v)
{
GraphNode* w;
visited[v] = TRUE; // 정점 v의 방문 표시
printf("정점 %d -> ", v); // 방문한 정점 출력
for (w = g->adj_list[v]; w; w = w->link)// 인접 정점 탐색
if (!visited[w->vertex])
dfs_list(g, w->vertex); //정점 w에서 DFS 새로 시작
}
- 명시적인 스택을 이용한 깊이 우선 탐색 -
- 스택을 하나 생성하여 시작 정점을 스택에 넣는다
- 스택에서 하나의 정점을 꺼내서 탐색을 시작한다
- 정점을 방문한 후에 정점의 모든 인접 정점들을 스택에 추가한다
- 스택에 하나도 남지 않을 때까지 반복한다
- 깊이 우선 탐색의 시간복잡도 -
> 깊이 우선 탐색은 그래프의 모든 간선을 조사하므로 정점의 수가 n이고 간선의 수가 e인 그래프인 경우, 그래프가 인접 리스트로 표현되어 있다면 시간 복잡도가 O(n+e)이고, 인접 행렬로 표시되어 있다면 O(n^2)이다. 이는 희소 그래프인 경우 깊이 우선 탐색은 인접 리스트의 사용이 인접 행렬보다 시간적으로 유리함을 뜻한다.
너비 우선 탐색
> 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하여 순회하는 방법
> 너비 우선 탐색을 위해서는 가까운 거리에 있는 정점들을 차례대로 저장한 수에 꺼 낼 수 있는 자료구조인 큐를 사용한다. 알고리즘은 큐에서 정점을 꺼내서 정점을 방문하고 인접 정점들을 큐에 추가한다. 큐가 소진도리 때까지 동일한 코드를 반복한다.
- 너비 우선탐색, 인접행렬 사용
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_QUEUE_SIZE 10
typedef int element;
typedef struct { // 큐 타입
element queue[MAX_QUEUE_SIZE];
int front, rear;
} QueueType;
// 오류 함수
void error(char *message)
{
fprintf(stderr, "%s\n", message);
exit(1);
}
// 공백 상태 검출 함수
void queue_init(QueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(QueueType *q)
{
return (q->front == q->rear);
}
// 포화 상태 검출 함수
int is_full(QueueType *q)
{
return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}
// 삽입 함수
void enqueue(QueueType *q, element item)
{
if (is_full(q))
error("큐가 포화상태입니다");
q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
q->queue[q->rear] = item;
}
// 삭제 함수
element dequeue(QueueType *q)
{
if (is_empty(q))
error("큐가 공백상태입니다");
q->front = (q->front + 1) % MAX_QUEUE_SIZE;
return q->queue[q->front];
}
#define MAX_VERTICES 50
typedef struct GraphType {
int n; // 정점의 개수
int adj_mat[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int visited[MAX_VERTICES];
// 그래프 초기화
void graph_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 bfs_mat(GraphType* g, int v)
{
int w;
QueueType q;
queue_init(&q); // 큐 초기화
visited[v] = TRUE; // 정점 v 방문 표시
printf("%d 방문 -> ", v);
enqueue(&q, v); // 시작 정점을 큐에 저장
while (!is_empty(&q)) {
v = dequeue(&q); // 큐에 정점 추출
for (w = 0; w<g->n; w++) // 인접 정점 탐색
if (g->adj_mat[v][w] && !visited[w]) {
visited[w] = TRUE; // 방문 표시
printf("%d 방문 -> ", w);
enqueue(&q, w); // 방문한 정점을 큐에 저장
}
}
}
int main(void)
{
GraphType *g;
g = (GraphType *)malloc(sizeof(GraphType));
graph_init(g);
for (int i = 0; i<6; i++)
insert_vertex(g, i);
insert_edge(g, 0, 2);
insert_edge(g, 2, 1);
insert_edge(g, 2, 3);
insert_edge(g, 0, 4);
insert_edge(g, 4, 5);
insert_edge(g, 1, 5);
printf("너비 우선 탐색\n");
bfs_mat(g, 0);
printf("\n");
free(g);
return 0;
}
- 너비 우선 탐색의 구현, 인접 리스트 사용
void bfs_list(GraphType* g, int v)
{
GraphNode* w;
QueueType q;
init(&q); // 큐 초기화
visited[v] = TRUE; // 정점 v 방문 표시
printf("%d 방문 -> ", v);
enqueue(&q, v); // 시작정점을 큐에 저장
while (!is_empty(&q)) {
v = dequeue(&q); // 큐에 저장된 정점 선택
for (w = g->adj_list[v]; w; w = w->link) //인접 정점 탐색
if (!visited[w->vertex]) { // 미방문 정점 탐색
visited[w->vertex] = TRUE; // 방문 표시
printf("%d 방문 -> ", w->vextex);
enqueue(&q, w->vertex); //정점을 큐에 삽입
}
}
}
- 너비 우선 탐색의 시간복잡도
> 너비 우선 탐색은 그래프가 인접 리스트로 표현되어 있으면 전체 수행시간이 O(n+e)이면 인접 행렬로 표현되어 있는 경우 O(n^2)의 시간이 걸린다. 너비 우선 탐색도 깊이 우선 탐색과 같이 희소 그래프를 사용할 경우 인접 리스트를 사용하는 것이 효율적이다.