15_mst.c

Download
c 419 lines 11.7 KB 
  1/*
  2 * ์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ (Minimum Spanning Tree)
  3 * Kruskal, Prim, Union-Find
  4 *
  5 * ๊ทธ๋ž˜ํ”„์˜ ๋ชจ๋“  ์ •์ ์„ ์—ฐ๊ฒฐํ•˜๋Š” ์ตœ์†Œ ๊ฐ€์ค‘์น˜ ํŠธ๋ฆฌ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <limits.h>
 11#include <stdbool.h>
 12
 13#define INF INT_MAX
 14
 15/* =============================================================================
 16 * 1. Union-Find (Disjoint Set Union)
 17 * ============================================================================= */
 18
 19typedef struct {
 20    int* parent;
 21    int* rank;
 22    int size;
 23} UnionFind;
 24
 25UnionFind* uf_create(int n) {
 26    UnionFind* uf = malloc(sizeof(UnionFind));
 27    uf->parent = malloc(n * sizeof(int));
 28    uf->rank = calloc(n, sizeof(int));
 29    uf->size = n;
 30
 31    for (int i = 0; i < n; i++)
 32        uf->parent[i] = i;
 33
 34    return uf;
 35}
 36
 37void uf_free(UnionFind* uf) {
 38    free(uf->parent);
 39    free(uf->rank);
 40    free(uf);
 41}
 42
 43int uf_find(UnionFind* uf, int x) {
 44    if (uf->parent[x] != x)
 45        uf->parent[x] = uf_find(uf, uf->parent[x]);  /* ๊ฒฝ๋กœ ์••์ถ• */
 46    return uf->parent[x];
 47}
 48
 49bool uf_union(UnionFind* uf, int x, int y) {
 50    int px = uf_find(uf, x);
 51    int py = uf_find(uf, y);
 52
 53    if (px == py) return false;
 54
 55    /* ๋žญํฌ ๊ธฐ๋ฐ˜ ํ•ฉ์น˜๊ธฐ */
 56    if (uf->rank[px] < uf->rank[py]) {
 57        uf->parent[px] = py;
 58    } else if (uf->rank[px] > uf->rank[py]) {
 59        uf->parent[py] = px;
 60    } else {
 61        uf->parent[py] = px;
 62        uf->rank[px]++;
 63    }
 64
 65    return true;
 66}
 67
 68bool uf_connected(UnionFind* uf, int x, int y) {
 69    return uf_find(uf, x) == uf_find(uf, y);
 70}
 71
 72/* =============================================================================
 73 * 2. ๊ฐ„์„  ๊ตฌ์กฐ์ฒด
 74 * ============================================================================= */
 75
 76typedef struct {
 77    int src;
 78    int dest;
 79    int weight;
 80} Edge;
 81
 82int compare_edges(const void* a, const void* b) {
 83    return ((Edge*)a)->weight - ((Edge*)b)->weight;
 84}
 85
 86/* =============================================================================
 87 * 3. ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜
 88 * ============================================================================= */
 89
 90typedef struct {
 91    Edge* edges;
 92    int num_edges;
 93    int total_weight;
 94} MST;
 95
 96MST kruskal(int vertices, Edge edges[], int num_edges) {
 97    /* ๊ฐ„์„ ์„ ๊ฐ€์ค‘์น˜ ์ˆœ์œผ๋กœ ์ •๋ ฌ */
 98    qsort(edges, num_edges, sizeof(Edge), compare_edges);
 99
100    UnionFind* uf = uf_create(vertices);
101    MST mst;
102    mst.edges = malloc((vertices - 1) * sizeof(Edge));
103    mst.num_edges = 0;
104    mst.total_weight = 0;
105
106    for (int i = 0; i < num_edges && mst.num_edges < vertices - 1; i++) {
107        int u = edges[i].src;
108        int v = edges[i].dest;
109
110        if (uf_union(uf, u, v)) {
111            mst.edges[mst.num_edges++] = edges[i];
112            mst.total_weight += edges[i].weight;
113        }
114    }
115
116    uf_free(uf);
117    return mst;
118}
119
120/* =============================================================================
121 * 4. ํ”„๋ฆผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋ฐฐ์—ด ๊ธฐ๋ฐ˜)
122 * ============================================================================= */
123
124MST prim_array(int** graph, int vertices) {
125    int* key = malloc(vertices * sizeof(int));      /* ์ตœ์†Œ ๊ฐ€์ค‘์น˜ */
126    int* parent = malloc(vertices * sizeof(int));   /* MST์—์„œ์˜ ๋ถ€๋ชจ */
127    bool* in_mst = calloc(vertices, sizeof(bool));
128
129    for (int i = 0; i < vertices; i++) {
130        key[i] = INF;
131        parent[i] = -1;
132    }
133
134    key[0] = 0;
135
136    for (int count = 0; count < vertices - 1; count++) {
137        /* ์ตœ์†Œ key ์ •์  ์ฐพ๊ธฐ */
138        int min_key = INF, u = -1;
139        for (int v = 0; v < vertices; v++) {
140            if (!in_mst[v] && key[v] < min_key) {
141                min_key = key[v];
142                u = v;
143            }
144        }
145
146        if (u == -1) break;
147        in_mst[u] = true;
148
149        /* ์ธ์ ‘ ์ •์  ๊ฐฑ์‹  */
150        for (int v = 0; v < vertices; v++) {
151            if (graph[u][v] && !in_mst[v] && graph[u][v] < key[v]) {
152                parent[v] = u;
153                key[v] = graph[u][v];
154            }
155        }
156    }
157
158    /* MST ๊ตฌ์„ฑ */
159    MST mst;
160    mst.edges = malloc((vertices - 1) * sizeof(Edge));
161    mst.num_edges = 0;
162    mst.total_weight = 0;
163
164    for (int i = 1; i < vertices; i++) {
165        if (parent[i] != -1) {
166            mst.edges[mst.num_edges].src = parent[i];
167            mst.edges[mst.num_edges].dest = i;
168            mst.edges[mst.num_edges].weight = graph[parent[i]][i];
169            mst.total_weight += graph[parent[i]][i];
170            mst.num_edges++;
171        }
172    }
173
174    free(key);
175    free(parent);
176    free(in_mst);
177    return mst;
178}
179
180/* =============================================================================
181 * 5. ํ”„๋ฆผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (์šฐ์„ ์ˆœ์œ„ ํ)
182 * ============================================================================= */
183
184typedef struct {
185    int vertex;
186    int key;
187} PQNode;
188
189typedef struct {
190    PQNode* data;
191    int size;
192    int capacity;
193} PriorityQueue;
194
195PriorityQueue* pq_create(int capacity) {
196    PriorityQueue* pq = malloc(sizeof(PriorityQueue));
197    pq->data = malloc(capacity * sizeof(PQNode));
198    pq->size = 0;
199    pq->capacity = capacity;
200    return pq;
201}
202
203void pq_push(PriorityQueue* pq, int vertex, int key) {
204    int i = pq->size++;
205    pq->data[i].vertex = vertex;
206    pq->data[i].key = key;
207
208    while (i > 0) {
209        int parent = (i - 1) / 2;
210        if (pq->data[parent].key <= pq->data[i].key) break;
211        PQNode temp = pq->data[parent];
212        pq->data[parent] = pq->data[i];
213        pq->data[i] = temp;
214        i = parent;
215    }
216}
217
218PQNode pq_pop(PriorityQueue* pq) {
219    PQNode min = pq->data[0];
220    pq->data[0] = pq->data[--pq->size];
221
222    int i = 0;
223    while (2 * i + 1 < pq->size) {
224        int smallest = i;
225        int left = 2 * i + 1;
226        int right = 2 * i + 2;
227
228        if (pq->data[left].key < pq->data[smallest].key)
229            smallest = left;
230        if (right < pq->size && pq->data[right].key < pq->data[smallest].key)
231            smallest = right;
232
233        if (smallest == i) break;
234
235        PQNode temp = pq->data[i];
236        pq->data[i] = pq->data[smallest];
237        pq->data[smallest] = temp;
238        i = smallest;
239    }
240
241    return min;
242}
243
244/* ์ธ์ ‘ ๋ฆฌ์ŠคํŠธ์šฉ ๊ตฌ์กฐ์ฒด */
245typedef struct AdjNode {
246    int dest;
247    int weight;
248    struct AdjNode* next;
249} AdjNode;
250
251MST prim_heap(AdjNode** adj, int vertices) {
252    int* key = malloc(vertices * sizeof(int));
253    int* parent = malloc(vertices * sizeof(int));
254    bool* in_mst = calloc(vertices, sizeof(bool));
255
256    for (int i = 0; i < vertices; i++) {
257        key[i] = INF;
258        parent[i] = -1;
259    }
260
261    PriorityQueue* pq = pq_create(vertices * vertices);
262    key[0] = 0;
263    pq_push(pq, 0, 0);
264
265    while (pq->size > 0) {
266        PQNode node = pq_pop(pq);
267        int u = node.vertex;
268
269        if (in_mst[u]) continue;
270        in_mst[u] = true;
271
272        AdjNode* neighbor = adj[u];
273        while (neighbor) {
274            int v = neighbor->dest;
275            int w = neighbor->weight;
276
277            if (!in_mst[v] && w < key[v]) {
278                key[v] = w;
279                parent[v] = u;
280                pq_push(pq, v, w);
281            }
282            neighbor = neighbor->next;
283        }
284    }
285
286    MST mst;
287    mst.edges = malloc((vertices - 1) * sizeof(Edge));
288    mst.num_edges = 0;
289    mst.total_weight = 0;
290
291    for (int i = 1; i < vertices; i++) {
292        if (parent[i] != -1) {
293            mst.edges[mst.num_edges].src = parent[i];
294            mst.edges[mst.num_edges].dest = i;
295            mst.edges[mst.num_edges].weight = key[i];
296            mst.total_weight += key[i];
297            mst.num_edges++;
298        }
299    }
300
301    free(key);
302    free(parent);
303    free(in_mst);
304    free(pq->data);
305    free(pq);
306    return mst;
307}
308
309/* =============================================================================
310 * 6. Union-Find ์‘์šฉ: ์—ฐ๊ฒฐ ์š”์†Œ
311 * ============================================================================= */
312
313int count_components(int n, int edges[][2], int num_edges) {
314    UnionFind* uf = uf_create(n);
315
316    for (int i = 0; i < num_edges; i++) {
317        uf_union(uf, edges[i][0], edges[i][1]);
318    }
319
320    int count = 0;
321    for (int i = 0; i < n; i++) {
322        if (uf->parent[i] == i) count++;
323    }
324
325    uf_free(uf);
326    return count;
327}
328
329/* =============================================================================
330 * ํ…Œ์ŠคํŠธ
331 * ============================================================================= */
332
333int main(void) {
334    printf("============================================================\n");
335    printf("์ตœ์†Œ ์‹ ์žฅ ํŠธ๋ฆฌ (MST) ์˜ˆ์ œ\n");
336    printf("============================================================\n");
337
338    /* 1. Union-Find */
339    printf("\n[1] Union-Find ๊ธฐ๋ณธ\n");
340    UnionFind* uf = uf_create(6);
341    printf("    union(0, 1): %s\n", uf_union(uf, 0, 1) ? "ํ•ฉ์นจ" : "์ด๋ฏธ ์—ฐ๊ฒฐ๋จ");
342    printf("    union(2, 3): %s\n", uf_union(uf, 2, 3) ? "ํ•ฉ์นจ" : "์ด๋ฏธ ์—ฐ๊ฒฐ๋จ");
343    printf("    union(1, 2): %s\n", uf_union(uf, 1, 2) ? "ํ•ฉ์นจ" : "์ด๋ฏธ ์—ฐ๊ฒฐ๋จ");
344    printf("    connected(0, 3): %s\n", uf_connected(uf, 0, 3) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค");
345    printf("    connected(0, 5): %s\n", uf_connected(uf, 0, 5) ? "์˜ˆ" : "์•„๋‹ˆ์˜ค");
346    uf_free(uf);
347
348    /* 2. ํฌ๋ฃจ์Šค์นผ */
349    printf("\n[2] ํฌ๋ฃจ์Šค์นผ ์•Œ๊ณ ๋ฆฌ์ฆ˜\n");
350    Edge edges[] = {
351        {0, 1, 4}, {0, 7, 8}, {1, 2, 8}, {1, 7, 11},
352        {2, 3, 7}, {2, 8, 2}, {2, 5, 4}, {3, 4, 9},
353        {3, 5, 14}, {4, 5, 10}, {5, 6, 2}, {6, 7, 1},
354        {6, 8, 6}, {7, 8, 7}
355    };
356
357    printf("    ๊ฐ„์„  ์ˆ˜: 14, ์ •์  ์ˆ˜: 9\n");
358    MST mst1 = kruskal(9, edges, 14);
359    printf("    MST ๊ฐ„์„ :\n");
360    for (int i = 0; i < mst1.num_edges; i++) {
361        printf("      %d - %d (๊ฐ€์ค‘์น˜ %d)\n",
362               mst1.edges[i].src, mst1.edges[i].dest, mst1.edges[i].weight);
363    }
364    printf("    ์ด ๊ฐ€์ค‘์น˜: %d\n", mst1.total_weight);
365    free(mst1.edges);
366
367    /* 3. ํ”„๋ฆผ (๋ฐฐ์—ด) */
368    printf("\n[3] ํ”„๋ฆผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (๋ฐฐ์—ด)\n");
369    int** graph = malloc(5 * sizeof(int*));
370    for (int i = 0; i < 5; i++) {
371        graph[i] = calloc(5, sizeof(int));
372    }
373    graph[0][1] = graph[1][0] = 2;
374    graph[0][3] = graph[3][0] = 6;
375    graph[1][2] = graph[2][1] = 3;
376    graph[1][3] = graph[3][1] = 8;
377    graph[1][4] = graph[4][1] = 5;
378    graph[2][4] = graph[4][2] = 7;
379    graph[3][4] = graph[4][3] = 9;
380
381    MST mst2 = prim_array(graph, 5);
382    printf("    MST ๊ฐ„์„ :\n");
383    for (int i = 0; i < mst2.num_edges; i++) {
384        printf("      %d - %d (๊ฐ€์ค‘์น˜ %d)\n",
385               mst2.edges[i].src, mst2.edges[i].dest, mst2.edges[i].weight);
386    }
387    printf("    ์ด ๊ฐ€์ค‘์น˜: %d\n", mst2.total_weight);
388    free(mst2.edges);
389
390    for (int i = 0; i < 5; i++) free(graph[i]);
391    free(graph);
392
393    /* 4. ์—ฐ๊ฒฐ ์š”์†Œ ๊ฐœ์ˆ˜ */
394    printf("\n[4] ์—ฐ๊ฒฐ ์š”์†Œ ๊ฐœ์ˆ˜\n");
395    int comp_edges[][2] = {{0, 1}, {1, 2}, {3, 4}};
396    printf("    ์ •์ : 0-4, ๊ฐ„์„ : (0,1), (1,2), (3,4)\n");
397    printf("    ์—ฐ๊ฒฐ ์š”์†Œ ๊ฐœ์ˆ˜: %d\n", count_components(5, comp_edges, 3));
398
399    /* 5. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋น„๊ต */
400    printf("\n[5] ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋น„๊ต\n");
401    printf("    | ์•Œ๊ณ ๋ฆฌ์ฆ˜      | ์‹œ๊ฐ„๋ณต์žก๋„    | ์ ํ•ฉํ•œ ๊ทธ๋ž˜ํ”„ |\n");
402    printf("    |---------------|---------------|---------------|\n");
403    printf("    | ํฌ๋ฃจ์Šค์นผ      | O(E log E)    | ํฌ์†Œ ๊ทธ๋ž˜ํ”„   |\n");
404    printf("    | ํ”„๋ฆผ(๋ฐฐ์—ด)    | O(Vยฒ)         | ๋ฐ€์ง‘ ๊ทธ๋ž˜ํ”„   |\n");
405    printf("    | ํ”„๋ฆผ(ํž™)      | O(E log V)    | ํฌ์†Œ ๊ทธ๋ž˜ํ”„   |\n");
406
407    /* 6. Union-Find ๋ณต์žก๋„ */
408    printf("\n[6] Union-Find ๋ณต์žก๋„\n");
409    printf("    | ์—ฐ์‚ฐ     | ์‹œ๊ฐ„๋ณต์žก๋„      |\n");
410    printf("    |----------|----------------|\n");
411    printf("    | find     | O(ฮฑ(n)) โ‰ˆ O(1) |\n");
412    printf("    | union    | O(ฮฑ(n)) โ‰ˆ O(1) |\n");
413    printf("    | ฮฑ(n): ์—ญ์•„์ปค๋งŒ ํ•จ์ˆ˜ (๋งค์šฐ ๋Š๋ฆฌ๊ฒŒ ์ฆ๊ฐ€)\n");
414
415    printf("\n============================================================\n");
416
417    return 0;
418}