물마시니의 구구절절

얍 붸붸

크리스마트 트리 장식을 입수했다는

나머지 장식은 그냥 대충 준비를 해놓고

가장 중요한 나무를

-_-…….벌목해야 될 판이라는

후후후…… 전원 넣어보니까 불이 잘 들어온다는 +_+

다양한 모드로 불 켤 수가 있게 되어있는데

이거 잘만하면 꽤나 재미있게 써먹을 수 있겠다 ㅋㅋㅋ +_+ 야호~~

이번에 이산수학 과제로 나온 최소 비용 신장 트리……

그래프 알고리즘에서 꽤나 많이 쓰인다는데……

(물론 다양하게 응용 가능?!)

이게 꽤나 머리를 써야 만드는 알고리즘이라서

일단 이해 하면서 외우는 방향으로 코딩하였다.

에휴 이런 알고리즘을 듣자마자 바로 짤수 있다면 얼마나 좋을까?

신이시여 나에게 천재적 재능을 제발;;;;;

자세한 소스는 밑에서 계속~

[spoiler]

#include <stdio.h>

#include <malloc.h>

typedef struct edge // 간선을 나타내는 구조체

{

int vertex[2]; // 시작점과 끝점

int cost; // 가중치

}Edge;

int **make_array(int n);// 배열 만들기

void read_array(FILE *file, int *G[], int n);// 파일에서 배열값 읽기

void convert_array_to_edge(int* G[], Edge E[], int n);// 배열을 간선으로 변환

void convert_edge_to_array(int* G[], Edge E[], int n, int m);// 간선을 배열로 변환

void print_edgy(Edge E[], int n);// 간선 집합 출력

void kruskal(int n, int m, Edge E[], Edge F[]);// 크루스칼 알고리즘

void bubble_sort(Edge E[], int m);// 거품 정렬

void find_merge(int p, int q, int U[]);// 집합을 합치는 함수

int find_set(int i, int U[]);// 해당 정점이 어떤 집합에 속하는지 찾는 함수

int main()

{

int n, m; // n개의 정점과 m개의 간선을 저장할 변수

int **G; // 더블 포인터로 동적 배열을 생성할 변수 선언

int **result; // 최소신장 트리를 인접배열로 나타내기 위한 변수 선언


Edge *E, *F;

FILE* file;

file = fopen(”kruskal_array.txt”, “r”);

if(file == NULL) {

perror(”File open error”);

return 0;

}

fscanf(file, “%d %d”, &n, &m); // 파일로부터 m, n을 입력 받는다

E = (Edge *) malloc(sizeof(Edge)*(m-1)); // 처음 입력 받은 배열을 간선으로 저장하기 위한 Edge

F = (Edge *) malloc(sizeof(Edge)*(n-2)); // 최소비용 신장트리 결과를 저장할 Edge

G = make_array(n); // 배열 만들기

result = make_array(n);

read_array(file, G, n); // 파일에서 배열 정보 읽기

convert_array_to_edge(G, E, n); // 배열 정보를 간선 정보로 변환

printf(”\n## Kruskal 최소 비용 신장 트리 ##\n”); // 크루스칼 알고리즘을 돌린 최소 비용 신장 트리를 F 간선 집합에 삽입

kruskal(n, m, E, F); // 최소 비용 신장 트리 결과 출력

printf(”\n최소 비용 신장 트리 결과\n”);

print_edgy(F, n);

printf(”\n최소 비용 신장 트리 결과(인접 배열)\n”);

convert_edge_to_array(result, F, n, m); // n-1개의 간선이 F에 포함되므로

fclose(file);

return 0;

}

void print_edgy(Edge E[], int n) // 간선 집합 출력

{

int i;

for(i = 0; i < n; i++) {

if(E[i].cost != 0)

printf(”v%d -> v%d, 가중치 = %d\n”, E[i].vertex[0]+1, E[i].vertex[1]+1, E[i].cost);

}

}

int** make_array(int n) // N x N 배열 만들기

{

int i, j;

int** array; // N x N 동적 배열을 할당받을 더블 포인터 변수를 선언

n–;

array = (int**)malloc(sizeof(int*)*n);

for(i = 0; i <= n; i++) {

array[i] = (int*)malloc(sizeof(int)*n);

}


for (i = 0; i <= n; i++) {

for (j = 0; j <= n; j++) {

array[i][j] = 0;

}

}


return array; // array의 주소값을 반환해준다

}

void read_array(FILE *file, int *G[], int n) // 파일에서 배열 값을 읽어 배열 G에 저장

{

int i, j;

for(i = 0; i < n; i++) {

for(j = 0; j < n; j++) {

fscanf(file, “%d”, &G[i][j]);

}

}

}

void convert_array_to_edge(int *G[], Edge E[], int n)// 배열 정보를 간선 정보로 변환

{

int i, j, num = 0;

for(i = 0; i < n; i++) { // 배열의 정보를 간선 구조체에 삽입

for(j = i; j < n; j++) {

if( G[i][j] != 0 && G[i][j] != 99 ) { // 가중치의 값이 1에서 99 사이로 존재할때

E[num].vertex[0] = i; // i를 배열 첫번째 요소에 넣는다(간선의 시작점)

E[num].vertex[1] = j; // j를 배열 두번째 요소에 넣는다(간선의 끝점)

E[num].cost = G[i][j]; // 가중치를 넣는다

num++; // E의 다음배열을 증가시켜준다

}

}

}

}

void convert_edge_to_array(int* G[], Edge F[], int n, int m)

{

int i, j;

int sum = 0;

int num = 0;

while (num < m) {

for (i = 0; i < n; i++) {

if (F[num].vertex[0] == i) {

for (j = 0; j < n; j++) {

if (F[num].vertex[1] == j) {

G[j][i] = F[num].cost;

G[i][j] = F[num].cost;

sum += F[num].cost;

continue;

}

}

}

}

num++;

}

for (i = 0; i < n; i++) {

for (j = 0; j < n; j++) {

printf(”%2d “, G[i][j]);

}

printf(”\n”);

}

printf(”총비용 : %d\n”, sum);

}

void kruskal(int n, int m, Edge E[], Edge F[]) // 크루스칼 알고리즘

{

int start_vertex, end_vertax, i, current_edge;

int p, q; // 서로소 체크를 위한 집합을 가리키는 변수

int num = 0;

int* U = (int*)malloc(sizeof(int)*(n-1)); // 집합 선언

Edge edge_temp;

printf(”\n정렬 전 Edge E\n”);

print_edgy(E, m);

bubble_sort(E, m); // E에 속한 m개의 간선을 가중치가 작은 것부터 차례로 정렬

printf(”\n정렬 후 Edge E\n”);

print_edgy(E, m);

for (i = 0; i < n; i++) {// 집합 Initialize

U[i] = i;

}

current_edge = 0;

while(num < n-1) { // 간선의 수가 n-1보다 작을 동안

edge_temp = E[current_edge]; // 아직 고려하지 않은 간선 중 가중치가 최소인 간선

start_vertex = E[current_edge].vertex[0]; // i, j = e에 연결된 정점

end_vertax = E[current_edge].vertex[1];

p = find_set(start_vertex, U); // start_vertax가 속하는 집합을 p에 저장

q = find_set(end_vertax, U); // end_vertax가 속하는 집합을 q에 저장

if(p != q ) { // p와 q 가 서로 속한 집합이 다르다면

find_merge(p, q, U); // p, q가 속한 집합을 합침

F[num] = edge_temp; // edge_temp를 F에 추가

num++;

}

current_edge++;

}

}

int find_set(int i, int U[]) // i가 집합 U의 어느 집합에 속하나?

{

int j;

j = i;

while(U[j] != j) {

j = U[j];

}

return j;

}

void find_merge(int p, int q, int U[]) // p, q를 집합 U에 합칩

{

if (p < q) { // p는 합병된 집합을 가리키는 포인터

U[q] = p; // q는 더 이상 집합을 가리키는 포인터가 아님

}

else {

U[p] = q;

}

}

void bubble_sort(Edge E[], int m) // E 엣지 집합의 가중치를 정렬하기 위한 함수

{

int i, Sorted = 0;

Edge tmp;

while( !S
orted ) {// 정렬이 완료되지 않았으면

Sorted = 1;

for(i = 1; i < m; i++) {

if( E[i-1].cost > E[i].cost ) {

tmp = E[i-1];

E[i-1] = E[i];

E[i] = tmp;

Sorted = 0;

}

}

}

}

[/spoiler]