그 외 공부/Algorithm
# 13_MST(Minimum spanning tree)
ssangeun
2017. 11. 20. 20:32
# The source code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157 |
#include <stdio.h>
#include <stdlib.h>
#define NUM_VERTEX 5
#define NUM_EDGES 8
struct node
{
int v;
int weight;
struct node * next;
};
struct edge //sort를 위한
{
int from;
int to;
int w;
};
struct edge edges[NUM_EDGES]; //sort를 위한
struct node * graph[NUM_VERTEX];
/*----------cycle detection array------------*/
int cycle_detection[NUM_VERTEX] = { 0, 1, 2, 3, 4 };
/*----------cycle detection function------------*/
void putThemIntoSameGroup(int v1, int v2)
{
int g1 = cycle_detection[v1];
int g2 = cycle_detection[v2];
int smaller, bigger;
if (g1 > g2)
{
bigger = g1;
smaller = g2;
}
else
{
bigger = g2;
smaller = g1;
}
{
int i;
for (i = 0; i < NUM_VERTEX; i++)
{
if (cycle_detection[i] == bigger)
{
cycle_detection[i] = smaller;
}
}
}
}
void addEdge(int v1, int v2, int w, int reverse)
{
struct node *new_one = (struct node *)malloc(sizeof(struct node));
struct node *cur = graph[v1];
new_one->v = v2;
new_one->next = 0;
new_one->weight = w;
if (cur == 0)
{
graph[v1] = new_one;
}
else
{
while (cur->next != 0)
{
cur = cur->next;
}
cur->next = new_one;
}
if (reverse == 1)
{
addEdge(v2, v1, w, 0);
}
return;
}
void swap_edge(int e1, int e2)
{
struct edge temp;
temp = edges[e1];
edges[e1] = edges[e2];
edges[e2] = temp;
}
void sortEdges()
{
//모든 edge를 edges배열에 추가
int edges_index = 0;
int i;
struct node * cur = graph[0];
for (i = 0; i < NUM_VERTEX; i++)
{
cur = graph[i];
while (cur != 0)
{
edges[edges_index].from = i;
edges[edges_index].to = cur->v;
edges[edges_index].w = cur->weight;
edges_index++;
cur = cur->next;
}
}
//오름차순으로 정렬 by bubble sort
{
int x, y;
for (y = 0; y < NUM_EDGES; y++)
{
for (x = 0; x < NUM_EDGES - 1 - y; x++)
{
if (edges[x].w > edges[x + 1].w)
{
swap_edge(x, x + 1);
}
}
}
}
}
void doMST()
{
int i;
int mst_edges = 0;
for (i = 0; i < NUM_EDGES; i++)
{
if (cycle_detection[edges[i].from] != cycle_detection[edges[i].to])
{
printf("MST edge %d ---- %d (%d) \n", edges[i].from, edges[i].to, edges[i].w);
mst_edges++;
if(mst_edges == NUM_VERTEX-1)
{
return;
}
putThemIntoSameGroup(edges[i].from, edges[i].to);
}
}
}
void main()
{
addEdge(0, 1, 1, 0);
addEdge(0, 2, 3, 0);
addEdge(0, 4, 5, 0);
addEdge(1, 2, 2, 0);
addEdge(1, 4, 4, 0);
addEdge(2, 4, 6, 0);
addEdge(2, 3, 7, 0);
addEdge(3, 4, 8, 0);
sortEdges();
doMST();
}
//MST 순서 : weight에 따른 sort, sorting한 순서를 따라 같은 집안 요소가 아닌 것들만 connect. |
cs |
# The result
