12_graph_basic.c

Download
c 462 lines 12.5 KB 
  1/*
  2 * κ·Έλž˜ν”„ 기초 (Graph Basics)
  3 * DFS, BFS, Graph Representation, Connected Components
  4 *
  5 * κ·Έλž˜ν”„ μžλ£Œκ΅¬μ‘°μ™€ κΈ°λ³Έ 탐색 μ•Œκ³ λ¦¬μ¦˜μž…λ‹ˆλ‹€.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11#include <string.h>
 12
 13#define MAX_VERTICES 100
 14
 15/* =============================================================================
 16 * 1. κ·Έλž˜ν”„ ν‘œν˜„ - 인접 리슀트
 17 * ============================================================================= */
 18
 19typedef struct AdjNode {
 20    int vertex;
 21    int weight;
 22    struct AdjNode* next;
 23} AdjNode;
 24
 25typedef struct {
 26    AdjNode** adj;
 27    int vertices;
 28    bool directed;
 29} Graph;
 30
 31Graph* graph_create(int vertices, bool directed) {
 32    Graph* g = malloc(sizeof(Graph));
 33    g->vertices = vertices;
 34    g->directed = directed;
 35    g->adj = calloc(vertices, sizeof(AdjNode*));
 36    return g;
 37}
 38
 39void graph_add_edge(Graph* g, int src, int dest, int weight) {
 40    AdjNode* node = malloc(sizeof(AdjNode));
 41    node->vertex = dest;
 42    node->weight = weight;
 43    node->next = g->adj[src];
 44    g->adj[src] = node;
 45
 46    if (!g->directed) {
 47        node = malloc(sizeof(AdjNode));
 48        node->vertex = src;
 49        node->weight = weight;
 50        node->next = g->adj[dest];
 51        g->adj[dest] = node;
 52    }
 53}
 54
 55void graph_free(Graph* g) {
 56    for (int i = 0; i < g->vertices; i++) {
 57        AdjNode* node = g->adj[i];
 58        while (node) {
 59            AdjNode* temp = node;
 60            node = node->next;
 61            free(temp);
 62        }
 63    }
 64    free(g->adj);
 65    free(g);
 66}
 67
 68void graph_print(Graph* g) {
 69    for (int i = 0; i < g->vertices; i++) {
 70        printf("    %d: ", i);
 71        AdjNode* node = g->adj[i];
 72        while (node) {
 73            printf("%d(%d) ", node->vertex, node->weight);
 74            node = node->next;
 75        }
 76        printf("\n");
 77    }
 78}
 79
 80/* =============================================================================
 81 * 2. 인접 ν–‰λ ¬
 82 * ============================================================================= */
 83
 84typedef struct {
 85    int** matrix;
 86    int vertices;
 87} AdjMatrix;
 88
 89AdjMatrix* matrix_create(int vertices) {
 90    AdjMatrix* m = malloc(sizeof(AdjMatrix));
 91    m->vertices = vertices;
 92    m->matrix = malloc(vertices * sizeof(int*));
 93    for (int i = 0; i < vertices; i++) {
 94        m->matrix[i] = calloc(vertices, sizeof(int));
 95    }
 96    return m;
 97}
 98
 99void matrix_add_edge(AdjMatrix* m, int src, int dest, int weight, bool directed) {
100    m->matrix[src][dest] = weight;
101    if (!directed)
102        m->matrix[dest][src] = weight;
103}
104
105void matrix_free(AdjMatrix* m) {
106    for (int i = 0; i < m->vertices; i++)
107        free(m->matrix[i]);
108    free(m->matrix);
109    free(m);
110}
111
112/* =============================================================================
113 * 3. DFS (깊이 μš°μ„  탐색)
114 * ============================================================================= */
115
116void dfs_recursive(Graph* g, int v, bool visited[]) {
117    visited[v] = true;
118    printf("%d ", v);
119
120    AdjNode* node = g->adj[v];
121    while (node) {
122        if (!visited[node->vertex])
123            dfs_recursive(g, node->vertex, visited);
124        node = node->next;
125    }
126}
127
128void dfs(Graph* g, int start) {
129    bool* visited = calloc(g->vertices, sizeof(bool));
130    dfs_recursive(g, start, visited);
131    free(visited);
132}
133
134/* μŠ€νƒ 기반 DFS */
135void dfs_iterative(Graph* g, int start) {
136    bool* visited = calloc(g->vertices, sizeof(bool));
137    int* stack = malloc(g->vertices * sizeof(int));
138    int top = -1;
139
140    stack[++top] = start;
141
142    while (top >= 0) {
143        int v = stack[top--];
144
145        if (!visited[v]) {
146            visited[v] = true;
147            printf("%d ", v);
148
149            AdjNode* node = g->adj[v];
150            while (node) {
151                if (!visited[node->vertex])
152                    stack[++top] = node->vertex;
153                node = node->next;
154            }
155        }
156    }
157
158    free(visited);
159    free(stack);
160}
161
162/* =============================================================================
163 * 4. BFS (λ„ˆλΉ„ μš°μ„  탐색)
164 * ============================================================================= */
165
166void bfs(Graph* g, int start) {
167    bool* visited = calloc(g->vertices, sizeof(bool));
168    int* queue = malloc(g->vertices * sizeof(int));
169    int front = 0, rear = 0;
170
171    visited[start] = true;
172    queue[rear++] = start;
173
174    while (front < rear) {
175        int v = queue[front++];
176        printf("%d ", v);
177
178        AdjNode* node = g->adj[v];
179        while (node) {
180            if (!visited[node->vertex]) {
181                visited[node->vertex] = true;
182                queue[rear++] = node->vertex;
183            }
184            node = node->next;
185        }
186    }
187
188    free(visited);
189    free(queue);
190}
191
192/* BFS μ΅œλ‹¨ 거리 */
193int* bfs_distances(Graph* g, int start) {
194    int* dist = malloc(g->vertices * sizeof(int));
195    for (int i = 0; i < g->vertices; i++)
196        dist[i] = -1;
197
198    int* queue = malloc(g->vertices * sizeof(int));
199    int front = 0, rear = 0;
200
201    dist[start] = 0;
202    queue[rear++] = start;
203
204    while (front < rear) {
205        int v = queue[front++];
206
207        AdjNode* node = g->adj[v];
208        while (node) {
209            if (dist[node->vertex] == -1) {
210                dist[node->vertex] = dist[v] + 1;
211                queue[rear++] = node->vertex;
212            }
213            node = node->next;
214        }
215    }
216
217    free(queue);
218    return dist;
219}
220
221/* =============================================================================
222 * 5. μ—°κ²° μš”μ†Œ
223 * ============================================================================= */
224
225int count_connected_components(Graph* g) {
226    bool* visited = calloc(g->vertices, sizeof(bool));
227    int count = 0;
228
229    for (int i = 0; i < g->vertices; i++) {
230        if (!visited[i]) {
231            dfs_recursive(g, i, visited);
232            count++;
233        }
234    }
235
236    free(visited);
237    return count;
238}
239
240/* =============================================================================
241 * 6. 사이클 탐지
242 * ============================================================================= */
243
244/* 무방ν–₯ κ·Έλž˜ν”„ 사이클 탐지 */
245bool has_cycle_undirected_util(Graph* g, int v, bool visited[], int parent) {
246    visited[v] = true;
247
248    AdjNode* node = g->adj[v];
249    while (node) {
250        if (!visited[node->vertex]) {
251            if (has_cycle_undirected_util(g, node->vertex, visited, v))
252                return true;
253        } else if (node->vertex != parent) {
254            return true;
255        }
256        node = node->next;
257    }
258
259    return false;
260}
261
262bool has_cycle_undirected(Graph* g) {
263    bool* visited = calloc(g->vertices, sizeof(bool));
264
265    for (int i = 0; i < g->vertices; i++) {
266        if (!visited[i]) {
267            if (has_cycle_undirected_util(g, i, visited, -1)) {
268                free(visited);
269                return true;
270            }
271        }
272    }
273
274    free(visited);
275    return false;
276}
277
278/* λ°©ν–₯ κ·Έλž˜ν”„ 사이클 탐지 (3색 μ•Œκ³ λ¦¬μ¦˜) */
279bool has_cycle_directed_util(Graph* g, int v, int color[]) {
280    color[v] = 1;  /* νšŒμƒ‰: 처리 쀑 */
281
282    AdjNode* node = g->adj[v];
283    while (node) {
284        if (color[node->vertex] == 1)
285            return true;  /* νšŒμƒ‰ λ…Έλ“œ 발견 = 사이클 */
286        if (color[node->vertex] == 0) {
287            if (has_cycle_directed_util(g, node->vertex, color))
288                return true;
289        }
290        node = node->next;
291    }
292
293    color[v] = 2;  /* 검은색: μ™„λ£Œ */
294    return false;
295}
296
297bool has_cycle_directed(Graph* g) {
298    int* color = calloc(g->vertices, sizeof(int));
299
300    for (int i = 0; i < g->vertices; i++) {
301        if (color[i] == 0) {
302            if (has_cycle_directed_util(g, i, color)) {
303                free(color);
304                return true;
305            }
306        }
307    }
308
309    free(color);
310    return false;
311}
312
313/* =============================================================================
314 * 7. 이뢄 κ·Έλž˜ν”„ νŒλ³„
315 * ============================================================================= */
316
317bool is_bipartite(Graph* g) {
318    int* color = malloc(g->vertices * sizeof(int));
319    for (int i = 0; i < g->vertices; i++)
320        color[i] = -1;
321
322    int* queue = malloc(g->vertices * sizeof(int));
323
324    for (int start = 0; start < g->vertices; start++) {
325        if (color[start] != -1) continue;
326
327        int front = 0, rear = 0;
328        queue[rear++] = start;
329        color[start] = 0;
330
331        while (front < rear) {
332            int v = queue[front++];
333
334            AdjNode* node = g->adj[v];
335            while (node) {
336                if (color[node->vertex] == -1) {
337                    color[node->vertex] = 1 - color[v];
338                    queue[rear++] = node->vertex;
339                } else if (color[node->vertex] == color[v]) {
340                    free(color);
341                    free(queue);
342                    return false;
343                }
344                node = node->next;
345            }
346        }
347    }
348
349    free(color);
350    free(queue);
351    return true;
352}
353
354/* =============================================================================
355 * ν…ŒμŠ€νŠΈ
356 * ============================================================================= */
357
358int main(void) {
359    printf("============================================================\n");
360    printf("κ·Έλž˜ν”„ 기초 (Graph Basics) 예제\n");
361    printf("============================================================\n");
362
363    /* 1. κ·Έλž˜ν”„ 생성 */
364    printf("\n[1] κ·Έλž˜ν”„ 생성 (인접 리슀트)\n");
365    Graph* g = graph_create(6, false);
366    graph_add_edge(g, 0, 1, 1);
367    graph_add_edge(g, 0, 2, 1);
368    graph_add_edge(g, 1, 2, 1);
369    graph_add_edge(g, 1, 3, 1);
370    graph_add_edge(g, 2, 4, 1);
371    graph_add_edge(g, 3, 4, 1);
372    graph_add_edge(g, 4, 5, 1);
373
374    printf("    κ·Έλž˜ν”„ ꡬ쑰:\n");
375    graph_print(g);
376
377    /* 2. DFS */
378    printf("\n[2] DFS (0μ—μ„œ μ‹œμž‘)\n");
379    printf("    μž¬κ·€: ");
380    dfs(g, 0);
381    printf("\n");
382    printf("    반볡: ");
383    dfs_iterative(g, 0);
384    printf("\n");
385
386    /* 3. BFS */
387    printf("\n[3] BFS (0μ—μ„œ μ‹œμž‘)\n");
388    printf("    μˆœμ„œ: ");
389    bfs(g, 0);
390    printf("\n");
391
392    int* distances = bfs_distances(g, 0);
393    printf("    거리: ");
394    for (int i = 0; i < 6; i++)
395        printf("%d->%d ", i, distances[i]);
396    printf("\n");
397    free(distances);
398
399    /* 4. μ—°κ²° μš”μ†Œ */
400    printf("\n[4] μ—°κ²° μš”μ†Œ\n");
401    printf("    ν˜„μž¬ κ·Έλž˜ν”„: %d개\n", count_connected_components(g));
402
403    Graph* g2 = graph_create(6, false);
404    graph_add_edge(g2, 0, 1, 1);
405    graph_add_edge(g2, 2, 3, 1);
406    graph_add_edge(g2, 4, 5, 1);
407    printf("    λΆ„λ¦¬λœ κ·Έλž˜ν”„: %d개\n", count_connected_components(g2));
408    graph_free(g2);
409
410    /* 5. 사이클 탐지 */
411    printf("\n[5] 사이클 탐지\n");
412    printf("    무방ν–₯ κ·Έλž˜ν”„ 사이클: %s\n",
413           has_cycle_undirected(g) ? "있음" : "μ—†μŒ");
414
415    Graph* dag = graph_create(4, true);
416    graph_add_edge(dag, 0, 1, 1);
417    graph_add_edge(dag, 1, 2, 1);
418    graph_add_edge(dag, 2, 3, 1);
419    printf("    λ°©ν–₯ κ·Έλž˜ν”„ (DAG) 사이클: %s\n",
420           has_cycle_directed(dag) ? "있음" : "μ—†μŒ");
421
422    graph_add_edge(dag, 3, 1, 1);  /* 사이클 μΆ”κ°€ */
423    printf("    λ°©ν–₯ κ·Έλž˜ν”„ (with cycle) 사이클: %s\n",
424           has_cycle_directed(dag) ? "있음" : "μ—†μŒ");
425    graph_free(dag);
426
427    /* 6. 이뢄 κ·Έλž˜ν”„ */
428    printf("\n[6] 이뢄 κ·Έλž˜ν”„ νŒλ³„\n");
429    Graph* bipartite = graph_create(4, false);
430    graph_add_edge(bipartite, 0, 1, 1);
431    graph_add_edge(bipartite, 0, 3, 1);
432    graph_add_edge(bipartite, 1, 2, 1);
433    graph_add_edge(bipartite, 2, 3, 1);
434    printf("    4κ°ν˜• κ·Έλž˜ν”„: %s\n",
435           is_bipartite(bipartite) ? "이뢄 κ·Έλž˜ν”„" : "이뢄 κ·Έλž˜ν”„ μ•„λ‹˜");
436
437    Graph* non_bipartite = graph_create(3, false);
438    graph_add_edge(non_bipartite, 0, 1, 1);
439    graph_add_edge(non_bipartite, 1, 2, 1);
440    graph_add_edge(non_bipartite, 2, 0, 1);
441    printf("    μ‚Όκ°ν˜• κ·Έλž˜ν”„: %s\n",
442           is_bipartite(non_bipartite) ? "이뢄 κ·Έλž˜ν”„" : "이뢄 κ·Έλž˜ν”„ μ•„λ‹˜");
443    graph_free(bipartite);
444    graph_free(non_bipartite);
445
446    graph_free(g);
447
448    /* 7. λ³΅μž‘λ„ μš”μ•½ */
449    printf("\n[7] κ·Έλž˜ν”„ μ•Œκ³ λ¦¬μ¦˜ λ³΅μž‘λ„\n");
450    printf("    | μ•Œκ³ λ¦¬μ¦˜     | μ‹œκ°„λ³΅μž‘λ„  | 곡간     |\n");
451    printf("    |--------------|-------------|----------|\n");
452    printf("    | DFS          | O(V + E)    | O(V)     |\n");
453    printf("    | BFS          | O(V + E)    | O(V)     |\n");
454    printf("    | μ—°κ²° μš”μ†Œ    | O(V + E)    | O(V)     |\n");
455    printf("    | 사이클 탐지  | O(V + E)    | O(V)     |\n");
456    printf("    | 이뢄 νŒλ³„    | O(V + E)    | O(V)     |\n");
457
458    printf("\n============================================================\n");
459
460    return 0;
461}