반응형
신장트리
그래프 내의 모든 정점을 포함하는 트리, n개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다.
Kruskal의 MST 알고리즘
Kruskal의 알고리즘은 탐욕적인 방법(greedy method)을 이용한다. Kruskal의 알고리즘은 최소 비용 신장 트리가 최소 비용의 간선으로 구성됨과 동시에 사이클을 포함하지 않는다는 조건에 근거하여, 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다. 이러한 과정을 반복함으로써 네트워크의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구할 수 있다. 오름차순 정렬 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾아서 현재의 최소 비용 신장 트리의 집합에 추가한다. 만약 사이클을 형성하면 그 간선은 제외된다.
union-find연산
union-find 연산은 Kruskal의 알고리즘에서만 사용되는 것은 아니고 일반적으로 널리 사용된다. union(x, y) 연산은 원소 x와 y가 속해있는 집합을 입력으로 받아 2개의 집합의 합집합을 만든다.
Kruskal의 최소 비용 신장 트리 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000
int parent[MAX_VERTICES]; // 부모 노드
// 초기화
void set_init(int n)
{
for (int i = 0; i<n; i++)
parent[i] = -1;
}
// curr가 속하는 집합을 반환한다.
int set_find(int curr)
{
if (parent[curr] == -1)
return curr; // 루트
while (parent[curr] != -1) curr = parent[curr];
return curr;
}
// 두개의 원소가 속한 집합을 합친다.
void set_union(int a, int b)
{
int root1 = set_find(a); // 노드 a의 루트를 찾는다.
int root2 = set_find(b); // 노드 b의 루트를 찾는다.
if (root1 != root2) // 합한다.
parent[root1] = root2;
}
struct Edge { // 간선을 나타내는 구조체
int start, end, weight;
};
typedef struct GraphType {
int n; // 간선의 개수
struct Edge edges[2 * MAX_VERTICES];
} GraphType;
// 그래프 초기화
void graph_init(GraphType* g)
{
g->n = 0;
for (int i = 0; i < 2 * MAX_VERTICES; i++) {
g->edges[i].start = 0;
g->edges[i].end = 0;
g->edges[i].weight = INF;
}
}
// 간선 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w)
{
g->edges[g->n].start = start;
g->edges[g->n].end = end;
g->edges[g->n].weight = w;
g->n++;
}
// qsort()에 사용되는 함수
int compare(const void* a, const void* b)
{
struct Edge* x = (struct Edge*)a;
struct Edge* y = (struct Edge*)b;
return (x->weight - y->weight);
}
// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType *g)
{
int edge_accepted = 0; // 현재까지 선택된 간선의 수
int uset, vset; // 정점 u와 정점 v의 집합 번호
struct Edge e;
set_init(g->n); // 집합 초기화
qsort(g->edges, g->n, sizeof(struct Edge), compare);
printf("크루스칼 최소 신장 트리 알고리즘 \n");
int i = 0;
while (edge_accepted < (g->n - 1)) // 간선의 수 < (n-1)
{
e = g->edges[i];
uset = set_find(e.start); // 정점 u의 집합 번호
vset = set_find(e.end); // 정점 v의 집합 번호
if (uset != vset) { // 서로 속한 집합이 다르면
printf("간선 (%d,%d) %d 선택\n", e.start, e.end, e.weight);
edge_accepted++;
set_union(uset, vset); // 두개의 집합을 합친다.
}
i++;
}
}
int main(void)
{
GraphType *g;
g = (GraphType *)malloc(sizeof(GraphType));
graph_init(g);
insert_edge(g, 0, 1, 29);
insert_edge(g, 1, 2, 16);
insert_edge(g, 2, 3, 12);
insert_edge(g, 3, 4, 22);
insert_edge(g, 4, 5, 27);
insert_edge(g, 5, 0, 10);
insert_edge(g, 6, 1, 15);
insert_edge(g, 6, 3, 18);
insert_edge(g, 6, 4, 25);
kruskal(g);
free(g);
return 0;
}
Prim의 MST 알고리즘
Kruskal의 알고리즘은 간선을 기반으로 하는 알고리즘인 반면 Prim의 알고리즘은 정점을 기반으로 하는 알고리즘이다. 또한 Kruskal의 알고리즘에서는 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최저 간선만을 선택하는 방법이었던데 반하여 Prim의 알고리즘은 이전 단계에서 만들어진 신장 트리를 확장하는 방식이다.
Prim의 최소 비용 신장 트리 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int selected[MAX_VERTICES];
int distance[MAX_VERTICES];
// 최소 dist[v] 값을 갖는 정점을 반환
int get_min_vertex(int n)
{
int v, i;
for (i = 0; i <n; i++)
if (!selected[i]) {
v = i;
break;
}
for (i = 0; i < n; i++)
if (!selected[i] && (distance[i] < distance[v])) v = i;
return (v);
}
//
void prim(GraphType* g, int s)
{
int i, u, v;
for (u = 0; u<g->n; u++)
distance[u] = INF;
distance[s] = 0;
for (i = 0; i<g->n; i++) {
u = get_min_vertex(g->n);
selected[u] = TRUE;
if (distance[u] == INF) return;
printf("정점 %d 추가\n", u);
for (v = 0; v<g->n; v++)
if (g->weight[u][v] != INF)
if (!selected[v] && g->weight[u][v]< distance[v])
distance[v] = g->weight[u][v];
}
}
int main(void)
{
GraphType g = { 7,
{{ 0, 29, INF, INF, INF, 10, INF },
{ 29, 0, 16, INF, INF, INF, 15 },
{ INF, 16, 0, 12, INF, INF, INF },
{ INF, INF, 12, 0, 22, INF, 18 },
{ INF, INF, INF, 22, 0, 27, 25 },
{ 10, INF, INF, INF, 27, 0, INF },
{ INF, 15, INF, 18, 25, INF, 0 } }
};
prim(&g, 0);
return 0;
}
Prim의 알고리즘의 분석
Prim의 알고리즘은 주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 Prim의 알고리즘은 O(n²)의 복잡도를 가진다. Kruskal의 알고리즘은 복잡도가 O(elog2e)이므로 희소 그래프를 대상으로 할 경우에는 Kruskal의 알고리즘이 적합하고, 밀집 그래프의 경우에는 Prim의 알고리즘이 유리하다고 할 수 있다.
Dijkstra의 알고리즘 구현
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int distance[MAX_VERTICES];/* 시작정점으로부터의 최단경로 거리 */
int found[MAX_VERTICES]; /* 방문한 정점 표시 */
int choose(int distance[], int n, int found[])
{
int i, min, minpos;
min = INT_MAX;
minpos = -1;
for (i = 0; i<n; i++)
if (distance[i]< min && !found[i]) {
min = distance[i];
minpos = i;
}
return minpos;
}
void print_status(GraphType* g)
{
static int step=1;
printf("STEP %d: ", step++);
printf("distance: ");
for (int i = 0; i < g->n; i++) {
if (distance[i] == INF)
printf(" * ");
else
printf("%2d ", distance[i]);
}
printf("\n");
printf(" found: ");
for (int i = 0; i<g->n; i++)
printf("%2d ", found[i]);
printf("\n\n");
}
//
void shortest_path(GraphType* g, int start)
{
int i, u, w;
for (i = 0; i<g->n; i++) /* 초기화 */
{
distance[i] = g->weight[start][i];
found[i] = FALSE;
}
found[start] = TRUE; /* 시작 정점 방문 표시 */
distance[start] = 0;
for (i = 0; i<g->n-1; i++) {
print_status(g);
u = choose(distance, g->n, found);
found[u] = TRUE;
for (w = 0; w<g->n; w++)
if (!found[w])
if (distance[u] + g->weight[u][w]<distance[w])
distance[w] = distance[u] + g->weight[u][w];
}
}
int main(void)
{
GraphType g = { 7,
{{ 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } }
};
shortest_path(&g, 0);
return 0;
}
Floyd의 최단 경로 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000000 /* 무한대 (연결이 없는 경우) */
typedef struct GraphType {
int n; // 정점의 개수
int weight[MAX_VERTICES][MAX_VERTICES];
} GraphType;
int A[MAX_VERTICES][MAX_VERTICES];
void printA(GraphType *g)
{
int i, j;
printf("===============================\n");
for (i = 0; i<g->n; i++) {
for (j = 0; j<g->n; j++) {
if (A[i][j] == INF)
printf(" * ");
else printf("%3d ", A[i][j]);
}
printf("\n");
}
printf("===============================\n");
}
void floyd(GraphType* g)
{
int i, j, k;
for (i = 0; i<g->n; i++)
for (j = 0; j<g->n; j++)
A[i][j] = g->weight[i][j];
printA(g);
for (k = 0; k<g->n; k++) {
for (i = 0; i<g->n; i++)
for (j = 0; j<g->n; j++)
if (A[i][k] + A[k][j] < A[i][j])
A[i][j] = A[i][k] + A[k][j];
printA(g);
}
}
int main(void)
{
GraphType g = { 7,
{{ 0, 7, INF, INF, 3, 10, INF },
{ 7, 0, 4, 10, 2, 6, INF },
{ INF, 4, 0, 2, INF, INF, INF },
{ INF, 10, 2, 0, 11, 9, 4 },
{ 3, 2, INF, 11, 0, INF, 5 },
{ 10, 6, INF, 9, INF, 0, INF },
{ INF, INF, INF, 4, 5, INF, 0 } }
};
floyd(&g);
return 0;
}
Floyd 최단 경로 알고리즘의 분석
Floyd의 알고리즘은 매우 간결한 반복 구문을 사용하므로 Dijkstra의 알고리즘 보다 상당히 빨리 모든 정점 간의 최단 경로를 찾을 수 있다.
위상 정렬
우리가 여태까지 해왔던 정렬이 '수' 를 정렬하는 것이었다면, 위상 정렬은 '그래프'를 정렬하는 것이고, 정렬 기준은 '진입 차수의 비 내림차순' 순서이다.
즉, 진입 차수가 0개 -> N개 순으로 탐색하고, 정렬 과정을 거치며 진입차수가 0인 노드들은 제거하고, 진입차수가 0이 아닌 노드들은 점점 0으로 수정한 뒤 제거해 가며 정렬을 하는 원리이다.
여기서 진입 차수란 해당 노드로 들어오는 간선의 개수이다.
예를 들어 A->B, C->B와 같은 형태의 그래프가 있다면 A, C의 진입 차수는 0, B의 진입 차수는 2가 된다.
단, 위상정렬이 가능하려면 DAG 그래프여야 한다.
DAG란 Directed Acyclic Graph의 약자로 '방향성이 있고, 사이클이 없는 그래프'를 의미한다.
그래프 위상 정렬 전체 프로그램
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#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 graph_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;
}
#define MAX_STACK_SIZE 100
typedef int element;
typedef struct {
element stack[MAX_STACK_SIZE];
int top;
} StackType;
// 스택 초기화 함수
void init(StackType *s)
{
s->top = -1;
}
// 공백 상태 검출 함수
int is_empty(StackType *s)
{
return (s->top == -1);
}
// 포화 상태 검출 함수
int is_full(StackType *s)
{
return (s->top == (MAX_STACK_SIZE - 1));
}
// 삽입함수
void push(StackType *s, element item)
{
if (is_full(s)) {
fprintf(stderr, "스택 포화 에러\n");
return;
}
else s->stack[++(s->top)] = item;
}
// 삭제함수
element pop(StackType *s)
{
if (is_empty(s)) {
fprintf(stderr, "스택 공백 에러\n");
exit(1);
}
else return s->stack[(s->top)--];
}
// 위상정렬을 수행한다.
int topo_sort(GraphType *g)
{
int i;
StackType s;
GraphNode *node;
// 모든 정점의 진입 차수를 계산
int *in_degree = (int *)malloc(g->n * sizeof(int));
for (i = 0; i < g->n; i++) // 초기화
in_degree[i] = 0;
for (i = 0; i < g->n; i++) {
GraphNode *node = g->adj_list[i];//정점 i에서 나오는 간선들
while (node != NULL) {
in_degree[node->vertex]++;
node = node->link;
}
}
// 진입 차수가 0인 정점을 스택에 삽입
init(&s);
for (i = 0; i < g->n; i++) {
if (in_degree[i] == 0) push(&s, i);
}
// 위상 순서를 생성
while (!is_empty(&s)) {
int w;
w = pop(&s);
printf("정점 %d ->", w); //정점 출력
node = g->adj_list[w]; //각 정점의 진입 차수를 변경
while (node != NULL) {
int u = node->vertex;
in_degree[u]--; //진입 차수를 감소
if (in_degree[u] == 0) push(&s, u);
node = node->link; // 다음 정점
}
}
free(in_degree);
printf("\n");
return (i == g->n); // 반환값이 1이면 성공, 0이면 실패
}
//
int main(void)
{
GraphType g;
graph_init(&g);
insert_vertex(&g, 0);
insert_vertex(&g, 1);
insert_vertex(&g, 2);
insert_vertex(&g, 3);
insert_vertex(&g, 4);
insert_vertex(&g, 5);
//정점 0의 인접 리스트 생성
insert_edge(&g, 0, 2);
insert_edge(&g, 0, 3);
//정점 1의 인접 리스트 생성
insert_edge(&g, 1, 3);
insert_edge(&g, 1, 4);
//정점 2의 인접 리스트 생성
insert_edge(&g, 2, 3);
insert_edge(&g, 2, 5);
//정점 3의 인접 리스트 생성
insert_edge(&g, 3, 5);
//정점 4의 인접 리스트 생성
insert_edge(&g, 4, 5);
//위상 정렬
topo_sort(&g);
// 동적 메모리 반환 코드 생략
return 0;
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 11장 연습문제 해설을 가져오도록 하겠습니다.
반응형