/*-----------ADT------------*/
void Init_Union(void); // parent와 num 배열을 초기화 한다.
void Union_gm(int s1, int s2); // s1, s2를 합집합으로 구성한다.
void Link_Vertex_gm(int s1, int s2, int key); // s1, s2의 합집합 여부를 검사한 뒤 그래프에추가한다.
/*--------------------------*/
void Init_Graph(Heap* h, int n); // n은 랜덤으로 생성되는 가중치의 최대값
// 그래프에 사용될 간선과 가중치를 랜덤으로 생성한 뒤, 최소 힙에 저장한다.
void Insert_Edge(int v1, int v2, int key, Heap* h); // 생성된 간선을 힙에 저장한다.
Heap* Init_Heap(void); // 최소 힙 트리를 구성하기 위한 구조체를 초기화 한다.
void Input_Heap(Edge* e, Heap* h); // 랜덤으로 생성된 간선을 최소 힙 트리에 저장하고 정렬한다.
Edge* Delete_Heap(Heap* h); // 트리에서 가장 작은 가중치를 가진 간선 주소를 반환한다.
void Print_Heap(Heap* h); // 트리 구성 여부를 확인하기 위한 함수
/*--------------------------*/
void Start_Kruskal(Heap* h);
// 가중치가 최소이고 현재 그래프의 정점들과 사이클을 이루지 않는 정점부터 그래프를 구성한다.
/*--------------------------*/
1. 두 정점의 합집합을 만들어줍니다.
두 정점을 한 집합으로 묶어줍니다.
두 정점 각각의 집합에 대해 원소의 수가 더 많은 정점의 집합에 다른 정점과 그 집합을 흡수시킵니다.
각 정점이 속한 집합의 가장 첫번째 정점을 부모 노드라고 하겠습니다.
해당 부모 노드에는 집합에 속한 정점의 갯수에 대한 정보가 포함됩니다.
자세한 내용은 아래의 주석을 확인해주세요.
void Init_Union(void) {
// parent를 -1로 num은 0으로 초기화 한다.
for (int i = 0; i < MAX_VERTEX; i++) {
parent[i] = -1;
num[i] = 0;
}
}
void Union_gm(int s1, int s2) {
// s1, s2 각각의 집합을 하나로 통합한다.
int u, v;
int p1, p2, s;
int tmp;
u = s1;
while (parent[u] != -1) { // s1의 속한 집합의 부모 노드(정점)를 찾는다.
u = parent[u];
}
v = s2;
while (parent[v] != -1) { // s2도 동일한 과정을 반복한다.
v = parent[v];
}
if (num[u] >= num[v]) { // 각각의 부모 노드를 기준으로 해당 집합에 속한 정점의 갯수를 비교한다.
p1 = u; // 딸린 정점이 더 많은 노드를 p1으로 설정한다.
p2 = v;
s = s2;
}
else {
p1 = v;
p2 = u;
s = s1;
}
parent[p2] = p1; // 딸린 정점이 더 많은 노드 p1의 집합으로 p2의 집합이 추가된다.
num[p1] += num[p2] + 1; // p1은 p2가 가진 자식 노드와 p2를 흡수한다.
while (parent[s] != -1) {
// s는 흡수된 집합의 정점이고, 아래와 같은 방법으로 자신과 연결된 모든 정점의 부모 노드를 p1으로 초기화해준다.
tmp = parent[s];
parent[s] = p1;
s = tmp;
}
}
2. 두 정점의 사이클 형성을 검사한 뒤, 간선 연결 여부를 결정합니다.
가장 연결 비용이 낮은 정점들부터 두 정점이 속한 집합을 비교합니다.
각 집합의 부모 노드가 동일하면 사이클을 형성하므로 두 정점을 잇지 않습니다.
void Link_Vertex_gm(int s1, int s2, int key) {
// s1, s2의 합집합 여부를 판단한 뒤, 간선 연결 여부를 결정한다.
int u, v;
u = s1;
while (parent[u] != -1) { // s1이 속한 집합의 부모 노드를 찾는다.
u = parent[u];
}
v = s2;
while (parent[v] != -1) { // s2가 속한 집합의 부모 노드를 찾는다.
v = parent[v];
}
if (u != v) { // 두 노드의 부모노드가 같이 않음 == 합집합이 아님 == 사이클을 형성하지 않음
Union_gm(s1, s2);
printf("Success Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
else {
printf("Fail Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
}
3. 그래프를 생성하기 위한 재료들을 만들어 줍니다.
최소 비용 신장 트리는 각 정점을 잇는 간선 중에 사이클을 형성하지 않으면서 비용을 최소로 하는 간선만 선택하여 연결된 트리입니다.
따라서, 모든 정점에 대해 각각을 연결하는 간선과 해당 간선의 비용을 랜덤으로 생성합니다.
랜덤으로 생성된 간선은 힙 트리에 저장됩니다.
이후 Kruskal 알고리즘 생성 시 가장 비용이 적은 간선부터 차례로 힙 트리에서 반환되어 그래프에 추가됩니다.
void Init_Graph(Heap* h, int n) {
// n을 최대값으로 갖는 랜덤 변수를 생성하고, 그 값을 가중치로 한 간선을 만든다.
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = 0; j < MAX_VERTEX; j++) {
ran_num = (rand() % n) + 1;
printf("n = %d\n", h->n);
printf("Random number: %d\n", ran_num);
Insert_Edge(i, j, ran_num, h); // 만들어진 간선을 Edge 구조체로 묶어준다.
}
}
}
void Insert_Edge(int v1, int v2, int key, Heap* h) {
// 랜덤 변수와 함께 만들어진 간선을 구조체로 묶고, 최소 힙 트리에 추가한다.
Edge* e = (Edge*)malloc(sizeof(Edge));
e->v1 = v1;
e->v2 = v2;
e->key = key;
Input_Heap(e, h);
}
4. 최소 힙 트리를 구성하기 위한 함수입니다.
힙 트리란 최소 또는 최대 값을 갖는 노드부터 완전 이진 트리에 차례로 저장되는 트리입니다.
재밌는 점은 입력과 삭제의 순서가 정해져있는 것입니다.
1) 입력: 트리의 가장 마지막에 새로운 노드를 저장하고, 부모 노드와 비교하며 제자리를 찾을 때까지 계속 올라갑니다.
2) 삭제: 트리의 가장 첫번째 노드를 삭제하고, 가장 마지막 노드가 첫번째 자리로 올라간 후 제자리를 찾을 때까지 자식 노드와 비교하며 내려갑니다.
아래 함수도 위와 같은 규칙에 따라 구현되었습니다.
Heap* Init_Heap(void) {
Heap* h = (Heap*)malloc(sizeof(Heap));
h->n = 0; // 힙 트리 내에 저장된 데이터의 갯수를 초기화해준다.
return h;
}
void Input_Heap(Edge* e, Heap* h) {
int i;
i = ++(h->n); // 새로운 노드가 추가되므로 전체 갯수를 하나 늘려주고 i에 저장합니다.
while (i != 1 && e->key < h->heap[i / 2]->key) {
// 첫번째 노드는 제외하고,
// 새로 들어온 노드의 가중치가 부모 노드의 가중치 보다 작을 때 반복문이 동작한다.
h->heap[i] = h->heap[i / 2];
// 부모 노드의 가중치가 자식 노드보다 크기 때문에 둘의 자리가 교환됩니다.
i /= 2;
// 부모 노드와 자식 노드의 위치 교환 후, i를 부모 노드가 있던 자리로 갱신해준다.
// 위로 올라가면서 부모와 자식 관계가 제대로 정렬될 때까지 반복한다.
}
h->heap[i] = e; // 마지막으로 교환된 부모 노드의 자리에 새로운 노드를 저장한다.
/*
1
2 3
4 5 6 ()
() 자리에 7번째 노드를 추가합니다.
7번 노드의 가중치는 1번 보다 크고 3번 보다 작다고 가정하겠습니다.
(1)
1
2 ()
4 5 6 3
(2)
1
2 7
4 5 6 3
이런식으로 ()의 위치가 위로 올라가다(i /= 2) 더이상 올라갈 자리가 없을 때 해당 자리(h->heap[i])에 e가 저장됩니다.
*/
}
Edge* Delete_Heap(Heap* h) {
// 힙 트리의 정점(첫번째 노드)에 있는 최소 가중치를 가진 간선 정보를 반환합니다.
int pr, ch;
Edge* re;
Edge* tmp;
re = h->heap[1]; // 항상 첫번째 노드가 반환 (return) 됩니다.
tmp = h->heap[(h->n)--]; // 마지막 노드를 tmp에 저장하고 전체 갯수를 1개 줄입니다.
// 항상 트리의 가장 마지막 노드가 첫번째 자리로 올라가고,
// 자식 노드와 크기를 비교하면서 부모-자식 관계가 바르게 정렬될 때 까지 내려갑니다.
pr = 1; // 부모 노드는 1
ch = 2; // 자식 노드는 2로 설정합니다.
while (ch <= h->n) { // 자식 노드가 트리 안에 있어야 합니다.
if (ch < h->n && h->heap[ch]->key > h->heap[ch + 1]->key)
/*
여기선 자식 노드의 크기를 비교합니다.
부모 노드보다 자식 노드의 크기가 더 작을 때
더 작은 자식 노드와 부모 노드의 자리가 변경되야 합니다.
while 문이 시작될 때 ch는 항상 짝수입니다.
따라서 ch+1은 같은 부모를 공유하는 ch의 오른쪽 형제 노드입니다.
ch가 크기가 더 크면, ch를 형제 노드의 인덱스로 갱신합니다. (최소 힙 트리)
*/
ch++;
if (tmp->key <= h->heap[ch]->key)
break;
// tmp->key에는 항상 마지막 노드의 가중치 정보가 저장되어 있습니다.
// 따라서, 자식 노드 보다 크기가 작거나 같을 때 while 문을 중지합니다.
// tmp
// ch ch+1
// 항상 위와 같은 관계에서 비교됩니다.
h->heap[pr] = h->heap[ch]; // 위에서 중지되지 않았으면, 자식과 부모의 자리를 교환합니다.
pr = ch; // 새로운 비교를 위해 pr과 ch를 갱신합니다.
ch *= 2;
}
h->heap[pr] = tmp; // pr 자리에 tmp를 저장하고 마무리합니다.
return re;
}
#endif
5. 힙 트리를 출력합니다.
힙 트리에 크기 순서대로 잘 정리되어 저장됐는지 확인하기 위한 함수입니다.
void Print_Heap(Heap* h) {
if (h->n != 0) {
printf("\n");
int n = 1;
for (int i = 1; i <= h->n; i++) {
printf("%3d ", h->heap[i]->key);
if (i == (int)pow(2, n) - 1) {
printf("\n");
n++;
}
}
printf("\n\n");
}
}
6. Kruskal 알고리즘을 실행합니다.
Kruskal 알고리즘은 다음과 같습니다.
1) 전체 간선 중에 가장 적은 비용을 가진 간선부터 차례로 출력한다.
2) 1)에서 출력된 간선이 기존 그래프의 간선과 사이클을 이루지 않을 때 그래프에 추가된다.
3) 모든 정점이 이어질 때까지 반복한다.
void Start_Kruskal(Heap* h) {
Edge* tmp;
Init_Union();
int n = h->n;
printf("n = %d\n", n);
for (int i = 0; i < n; i++) {
tmp = Delete_Heap(h);
// printf("Deleted_Value = %d\n", tmp->key);
// Print_Heap(h);
Link_Vertex_gm(tmp->v1, tmp->v2, tmp->key);
}
}
7. 전체 코드
//
// main.c
// Graph_MST_Kruskal
//
// Created by 김경민 on 2020/04/16.
// Copyright © 2020 김경민. All rights reserved.
// Kruskal 알고리즘을 사용해 최소 신장 트리를 구성한다.
// Minimum Spanning Tree
#include <stdio.h> // 표준 입출력 함수 라이브러리를 제공한다.
#include <stdlib.h> // malloc, rand, srand
#include <time.h> // time
#include <math.h> // pow
#define MAX_VERTEX 10
/*-----------Graph-----------*/ // 그래프의 각 정점과 연결되는 정점의 정보를 저장하기 위한 구조체
typedef struct LIST {
int vx; // 정점의 번호를 저장한다.
struct LIST* link; // 정점과 연결되는 모든 정점의 데이터를 저장한다.
}List;
typedef struct GRAPH {
int n; // 그래프에 연결되어 있는 정점의 갯수를 반환한다.
List* adj_list[MAX_VERTEX]; // 헤드 정점을 기준으로 인접한 정점의 데이터를 저장한다.
}Graph;
/*---------------------------*/
/*----------Kruskal----------*/
typedef struct EDGE { // 간선과 연결된 정점 데이터와 가중치를 저장하기 위한 구조체
int v1;
int v2;
int key;
}Edge;
typedef struct HEAP { // 가장 적은 비용을 가진 간선부터 차례로 그래프 포함 여부를 판별하기 위해서사용된다.
int n;
Edge* heap[MAX_VERTEX * MAX_VERTEX];
}Heap;
/*--------------------------*/
/*-----------Union-----------*/
// 그래프에 추가될 정점이 사이클을 이루는지 판별하기 위한 합집합 여부 검사 함수이다.
int parent[MAX_VERTEX];
int num[MAX_VERTEX];
/*---------------------------*/
/*-----------ADT------------*/
void Init_Union(void); // parent와 num 배열을 초기화 한다.
void Union_gm(int s1, int s2); // s1, s2를 합집합으로 구성한다.
void Link_Vertex_gm(int s1, int s2, int key); // s1, s2의 합집합 여부를 검사한 뒤 그래프에추가한다.
/*--------------------------*/
void Init_Graph(Heap* h, int n); // n은 랜덤으로 생성되는 가중치의 최대값
// 그래프에 사용될 간선과 가중치를 랜덤으로 생성한 뒤, 최소 힙에 저장한다.
void Insert_Edge(int v1, int v2, int key, Heap* h); // 생성된 간선을 힙에 저장한다.
Heap* Init_Heap(void); // 최소 힙 트리를 구성하기 위한 구조체를 초기화 한다.
void Input_Heap(Edge* e, Heap* h); // 랜덤으로 생성된 간선을 최소 힙 트리에 저장하고 정렬한다.
Edge* Delete_Heap(Heap* h); // 트리에서 가장 작은 가중치를 가진 간선 주소를 반환한다.
void Print_Heap(Heap* h); // 트리 구성 여부를 확인하기 위한 함수
/*--------------------------*/
void Start_Kruskal(Heap* h);
// 가중치가 최소이고 현재 그래프의 정점들과 사이클을 이루지 않는 정점부터 그래프를 구성한다.
/*--------------------------*/
int main(void) {
Heap* h = Init_Heap();
Init_Graph(h, 300);
Print_Heap(h);
#if 0
Edge* tmp;
for (int i = 0; i < MAX_VERTEX * MAX_VERTEX; i++) {
tmp = Delete_Heap(h);
printf("deleted_value %d -- %d = %d\n", tmp->v1, tmp->v2, tmp->key);
Print_Heap(h);
}
#endif
Start_Kruskal(h);
return 0;
}
void Init_Union(void) {
// parent를 -1로 num은 0으로 초기화 한다.
for (int i = 0; i < MAX_VERTEX; i++) {
parent[i] = -1;
num[i] = 0;
}
}
void Union_gm(int s1, int s2) {
// s1, s2를 같은 집합으로 넣어준다.
int u, v;
int p1, p2, s;
int tmp;
u = s1;
while (parent[u] != -1) { // s1과 연결된 노드 중에 가장 처음 연결된 노드를 찾는다.
u = parent[u]; // 즉, 연결된 노드를 줄 세웠을 때 가장 앞에 있는 노드이다.
}
v = s2;
while (parent[v] != -1) { // s2도 동일한 방법으로 집합의 가장 처음 노드를 찾아준다.
v = parent[v];
}
if (num[u] >= num[v]) { // 이때, u와 v는 s1, s2 각각 연결된 노드 중 가장 앞의 노드이다.
p1 = u; // 딸린 노드가 더 많은 노드를 p1으로 설정한다.
p2 = v;
s = s2;
}
else {
p1 = v;
p2 = u;
s = s1;
}
parent[p2] = p1; // 딸린 자식이 더 많은 노드 (p1)의 집합으로 p2가 추가된다.
num[p1] += num[p2] + 1; // p1은 p2가 가진 자식 노드와 p2를 포함하게 된다.
while (parent[s] != -1) {
// s는 p2의 자식이었고, 아래와 같은 방법으로 자신과 연결된 모든 노드의 부모 노드를 p1으로 초기화해준다.
tmp = parent[s];
parent[s] = p1;
s = tmp;
}
}
void Link_Vertex_gm(int s1, int s2, int key) {
// s1, s2의 합집합 여부를 판단한 뒤, 그래프 추가를 결정한다.
int u, v;
u = s1;
while (parent[u] != -1) {// s1의 부모노드가 나올 때까지 반복한다.
u = parent[u];
}
v = s2;
while (parent[v] != -1) {// s2의 부모노드가 나올 때까지 반복한다.
v = parent[v];
}
if (u != v) {// 두 노드의 부모노드가 같이 않음 == 합집합이 아님 == 사이클을 형성하지 않음
Union_gm(s1, s2);
printf("Success Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
else {
printf("Fail Link(key=%d): [%d] and [%d]\n\n", key, s1, s2);
}
}
void Init_Graph(Heap* h, int n) {
// n을 최대값으로 갖는 랜덤 변수를 생성하고, 그 값을 가중치로 한 간선을 만든다.
srand((unsigned int)time(NULL));
int ran_num;
for (int i = 0; i < MAX_VERTEX; i++) {
for (int j = 0; j < MAX_VERTEX; j++) {
ran_num = (rand() % n) + 1;
printf("n = %d\n", h->n);
printf("Random number: %d\n", ran_num);
Insert_Edge(i, j, ran_num, h); // 만들어진 간선을 구조체로 묶어준다.
}
}
}
void Insert_Edge(int v1, int v2, int key, Heap* h) {
// 랜덤 변수와 함께 만들어진 간선을 구조체로 묶고, 최소 힙 트리에 추가한다.
Edge* e = (Edge*)malloc(sizeof(Edge));
e->v1 = v1;
e->v2 = v2;
e->key = key;
Input_Heap(e, h);
}
Heap* Init_Heap(void) {
Heap* h = (Heap*)malloc(sizeof(Heap));
h->n = 0; // 힙 트리 내에 저장된 데이터의 갯수를 초기화해준다.
return h;
}
void Input_Heap(Edge* e, Heap* h) {
int i;
i = ++(h->n);
while (i != 1 && e->key < h->heap[i / 2]->key) {
// 첫번째 데이터는 제외하고,
// 새로 들어온 간선의 가중치가 부모 노드의 가중치 보다 작을 때 반복문이 동작한다.
h->heap[i] = h->heap[i / 2];
// 새로 들어갈 자리에 부모 노드의 주소가 저장된다.
i /= 2;
// 부모 노드와 자식 노드의 위치 변경 후에 i를 부모 노드 자리로 갱신해준다.
// 위로 올라가면서 부모와 자식 관계가 제대로 정렬될 때까지 반복한다.
}
h->heap[i] = e;
}
#if 0 // 동일한 최소 힙 트리 알고리즘이지만, 좀 더 직관적입니다.
void Input_Heap(Edge* e, Heap* h) {
if (h->n == 0) {
h->n++;
h->heap[h->n] = e;
}
else {
h->n++;
h->heap[h->n] = e;
int i = h->n;
Edge* tmp;
while (h->heap[i]->key < h->heap[i / 2]->key) {
tmp = h->heap[i / 2];
h->heap[i / 2] = h->heap[i];
h->heap[i] = tmp;
i = i / 2;
if (i == 1)
break;
}
}
}
#endif
Edge* Delete_Heap(Heap* h) {
// 힙 트리의 정점에 있는 최소 가중치를 가진 간선 정보를 반환합니다.
int pr, ch;
Edge* re;
Edge* tmp;
re = h->heap[1];// 무조건 가장 처음의 노드가 반환 (return) 됩니다.
tmp = h->heap[(h->n)--];
// 항상 트리의 가장 마지막 노드가 가장 처음 노드로 올라가고,
// 자식 노드와 크기를 비교하면서 부모-자식 관계가 바르게 정렬될 때 까지 내려갑니다.
pr = 1;// 부모 노드는 1
ch = 2;// 자식 노드는 2로 설정합니다.
while (ch <= h->n) {// 자식 노드가 트리 안에 있어야 합니다.
if (ch < h->n && h->heap[ch]->key > h->heap[ch + 1]->key)
// 여기선 자식 노드의 크기를 비교할 것입니다.
// 부모 노드보다 자식 노드의 크기가 더 작을 때
// 더 작은 자식 노드와 부모 노드의 자리가 변경되야 합니다.
// 따라서 ch < h->n 일 때 ch의 옆자리가 있기 때문에 자식 노드끼리 크기 비교가가능합니다.
// ch는 항상 짝수이고,
// 최소 힙 트리는 완전 이진 트리기 때문에 ch+1은 같은 부모를 공유하는 옆 자식 노드입니다.
// 따라서 ch가 크기가 더 크면, ch를 옆자리 자식 노드의 인덱스로 변경해줍니다.
ch++;
if (tmp->key <= h->heap[ch]->key)
break;
// tmp에는 가장 마지막 자리의 노드였던 노드의 가중치가 저장되어있습니다.
// tmp가 자신이 있는 위치의 자식 노드 보다 작을 때 정렬이 바르게 되어 있으므로
// 정렬을 중지합니다.
// tmp
// ch ch+1
// 위와 같이 세 노드는 관계를 이루고 있습니다.
h->heap[pr] = h->heap[ch]; // 위에서 정지 되지 않았으면, 자식을 위로 올려줍니다.
pr = ch;
ch *= 2;
// 이제 위로 올라간 노드의 자식과 크기 비교를 하기 위해 ch를 갱신해줍니다.
}
h->heap[pr] = tmp;
return re;
}
#if 0 // 마찬가지로 위 함수와 동일한 역할을 하지만, 보다 직관적입니다.
Edge* Delete_Heap(Heap* h) {
Edge* re;
re = h->heap[1];
h->heap[1] = h->heap[h->n--];
int i = 1;
Edge* tmp;
int u;
while (1) {
if (2 * i > h->n) {
break;
}
else {
u = 2 * i;
if (2 * i + 1 <= h->n) {
if (h->heap[2 * i]->key >= h->heap[2 * i + 1]->key) {
u = 2 * i + 1;
}
}
if (h->heap[i]->key > h->heap[u]->key) {
tmp = h->heap[u];
h->heap[u] = h->heap[i];
h->heap[i] = tmp;
i = u;
}
else {
break;
}
}
}
return re;
}
#endif
void Print_Heap(Heap* h) {
if (h->n != 0) {
printf("\n");
int n = 1;
for (int i = 1; i <= h->n; i++) {
printf("%3d ", h->heap[i]->key);
if (i == (int)pow(2, n) - 1) {
printf("\n");
n++;
}
}
printf("\n\n");
}
}
void Start_Kruskal(Heap* h) {
Edge* tmp;
Init_Union();
int n = h->n;
printf("n = %d\n", n);
for (int i = 0; i < n; i++) {
tmp = Delete_Heap(h);
// printf("Deleted_Value = %d\n", tmp->key);
// Print_Heap(h);
Link_Vertex_gm(tmp->v1, tmp->v2, tmp->key);
}
}
8. 실행 결과
아래 보다 더 길게 출력이 나옵니다.
꼭 확인해보세요.
'Programming > C' 카테고리의 다른 글
| [자료구조 C 언어] 부록 - 3: 최단 경로 알고리즘 - Dijkstra, Floyd (1) | 2020.05.14 |
|---|---|
| [자료구조 C 언어] 부록 - 2: 최소비용 신장트리 MST_Prim 알고리즘 (0) | 2020.05.14 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 19 : 네트워크 (AOV, AOE, EST, LST, critical path) (0) | 2020.03.19 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 18 : 그래프(4) 최단 거리 (shortest path) (1) | 2020.03.19 |
| [자료구조 C 언어] C 프로그래밍 자료구조 - 17 : 그래프(3) 최소 신장 트리 (MST): Kruskal, Prim 알고리즘 (0) | 2020.03.19 |