반응형
그래프
그래프는 정점(vertex)과 간선(edge)들의 유한 집합이라 할 수 있다. 수학적으로는 G = (V, E)와 같이 표시한다. 여기서, V(G)는 그래프 G의 정점들의 집합을, E(G)는 그래프 G의 간선들의 집합을 의미한다. 정점은 여러 가지 특성을 가질 수 있는 객체를 의미하고, 간선은 이렇나 정점들 간의 관계를 의미한다. 정점(vertex)은 노드(node)라고도 불리며, 간선(edge)은 링크(link)라고도 불린다.
V(G1) = { 0, 1, 2, 3 }
E(G1) = { (0, 1), (0, 2), (0, 3), (1, 2) }
무방향 그래프와 방향 그래프
무방향 그래프의 간선은 간선을 통해서 양방향으로 갈수 있음을 나타내며 정점 A와 정점 B를 연결하는 간선 (A, B)와 같이 정점의 쌍으로 표현한다. 방향 그래프는 간선에 방향성이 존재하는 그래프로서 도로의 일방통행길처럼 간선을 통하여 한쪽 방향으로만 갈 수 있음을 나타낸다.
(A, B) == (B, A) (O)
<A, B> == <B , A> (X)
완전 그래프
그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프를 완전 그래프(xomplete graph)라고 한다. 무방향 완전 그래프의 정점 수를 n이라고 하면, 하나의 정점은 n-1개의 다른 정점으로 연결되므로 간선의 수는 n*(n-1)/2가 된다. 만약 완전 그래프에서 n = 4라면 간선의 수는 (4*3)/2=6이다.
인접 행렬을 이용한 그래프 추상 데이터 타입의 구현
#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);
}
인접 리스트를 이용한 그래프 추상 데이터 타입의 구현
#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)은 트리에서 생각하면 이해하기 쉽다(트리도 그래프의 일종이라는 점을 명심하자). 트리를 탐색할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다.
인접 배열로 표현된 그래프에 대한 깊이우선탐색 프로그램
#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 새로 시작
}
너비 우선 탐색(BFS: breath first search)은 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
너비 우선 탐색(인접 행렬 표현) 프로그램
#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); //정점을 큐에 삽입
}
}
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 10장 연습문제 해설을 가져오도록 하겠습니다.
반응형