13_topological_sort.c

  1/*
  2 * 위상 정렬 (Topological Sort)
  3 * Kahn's Algorithm, DFS-based, Cycle Detection
  4 *
  5 * 방향 비순환 그래프(DAG)의 선형 순서를 찾습니다.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11
 12/* =============================================================================
 13 * 1. 그래프 구조
 14 * ============================================================================= */
 15
 16typedef struct AdjNode {
 17    int vertex;
 18    struct AdjNode* next;
 19} AdjNode;
 20
 21typedef struct {
 22    AdjNode** adj;
 23    int vertices;
 24} Graph;
 25
 26Graph* graph_create(int vertices) {
 27    Graph* g = malloc(sizeof(Graph));
 28    g->vertices = vertices;
 29    g->adj = calloc(vertices, sizeof(AdjNode*));
 30    return g;
 31}
 32
 33void graph_add_edge(Graph* g, int src, int dest) {
 34    AdjNode* node = malloc(sizeof(AdjNode));
 35    node->vertex = dest;
 36    node->next = g->adj[src];
 37    g->adj[src] = node;
 38}
 39
 40void graph_free(Graph* g) {
 41    for (int i = 0; i < g->vertices; i++) {
 42        AdjNode* node = g->adj[i];
 43        while (node) {
 44            AdjNode* temp = node;
 45            node = node->next;
 46            free(temp);
 47        }
 48    }
 49    free(g->adj);
 50    free(g);
 51}
 52
 53/* =============================================================================
 54 * 2. Kahn 알고리즘 (BFS 기반)
 55 * ============================================================================= */
 56
 57int* kahn_topological_sort(Graph* g, bool* has_cycle) {
 58    int* in_degree = calloc(g->vertices, sizeof(int));
 59    int* result = malloc(g->vertices * sizeof(int));
 60    int result_idx = 0;
 61
 62    /* 진입 차수 계산 */
 63    for (int v = 0; v < g->vertices; v++) {
 64        AdjNode* node = g->adj[v];
 65        while (node) {
 66            in_degree[node->vertex]++;
 67            node = node->next;
 68        }
 69    }
 70
 71    /* 진입 차수 0인 정점 큐에 추가 */
 72    int* queue = malloc(g->vertices * sizeof(int));
 73    int front = 0, rear = 0;
 74
 75    for (int i = 0; i < g->vertices; i++) {
 76        if (in_degree[i] == 0)
 77            queue[rear++] = i;
 78    }
 79
 80    /* BFS */
 81    while (front < rear) {
 82        int v = queue[front++];
 83        result[result_idx++] = v;
 84
 85        AdjNode* node = g->adj[v];
 86        while (node) {
 87            in_degree[node->vertex]--;
 88            if (in_degree[node->vertex] == 0)
 89                queue[rear++] = node->vertex;
 90            node = node->next;
 91        }
 92    }
 93
 94    *has_cycle = (result_idx != g->vertices);
 95
 96    free(in_degree);
 97    free(queue);
 98    return result;
 99}
100
101/* =============================================================================
102 * 3. DFS 기반 위상 정렬
103 * ============================================================================= */
104
105void dfs_topological_util(Graph* g, int v, bool visited[], int stack[], int* stack_top) {
106    visited[v] = true;
107
108    AdjNode* node = g->adj[v];
109    while (node) {
110        if (!visited[node->vertex])
111            dfs_topological_util(g, node->vertex, visited, stack, stack_top);
112        node = node->next;
113    }
114
115    stack[(*stack_top)++] = v;
116}
117
118int* dfs_topological_sort(Graph* g) {
119    bool* visited = calloc(g->vertices, sizeof(bool));
120    int* stack = malloc(g->vertices * sizeof(int));
121    int stack_top = 0;
122
123    for (int i = 0; i < g->vertices; i++) {
124        if (!visited[i])
125            dfs_topological_util(g, i, visited, stack, &stack_top);
126    }
127
128    /* 스택 역순으로 결과 생성 */
129    int* result = malloc(g->vertices * sizeof(int));
130    for (int i = 0; i < g->vertices; i++)
131        result[i] = stack[g->vertices - 1 - i];
132
133    free(visited);
134    free(stack);
135    return result;
136}
137
138/* =============================================================================
139 * 4. 사이클 탐지를 포함한 DFS 위상 정렬
140 * ============================================================================= */
141
142typedef enum { WHITE, GRAY, BLACK } Color;
143
144bool dfs_topological_cycle_util(Graph* g, int v, Color color[], int stack[], int* stack_top) {
145    color[v] = GRAY;
146
147    AdjNode* node = g->adj[v];
148    while (node) {
149        if (color[node->vertex] == GRAY)
150            return true;  /* 사이클 발견 */
151        if (color[node->vertex] == WHITE) {
152            if (dfs_topological_cycle_util(g, node->vertex, color, stack, stack_top))
153                return true;
154        }
155        node = node->next;
156    }
157
158    color[v] = BLACK;
159    stack[(*stack_top)++] = v;
160    return false;
161}
162
163int* dfs_topological_with_cycle(Graph* g, bool* has_cycle) {
164    Color* color = calloc(g->vertices, sizeof(Color));
165    int* stack = malloc(g->vertices * sizeof(int));
166    int stack_top = 0;
167
168    *has_cycle = false;
169    for (int i = 0; i < g->vertices; i++) {
170        if (color[i] == WHITE) {
171            if (dfs_topological_cycle_util(g, i, color, stack, &stack_top)) {
172                *has_cycle = true;
173                free(color);
174                free(stack);
175                return NULL;
176            }
177        }
178    }
179
180    int* result = malloc(g->vertices * sizeof(int));
181    for (int i = 0; i < g->vertices; i++)
182        result[i] = stack[g->vertices - 1 - i];
183
184    free(color);
185    free(stack);
186    return result;
187}
188
189/* =============================================================================
190 * 5. 모든 위상 정렬 찾기
191 * ============================================================================= */
192
193void all_topological_sorts_util(Graph* g, bool visited[], int in_degree[],
194                                 int result[], int idx, int* count) {
195    bool found = false;
196
197    for (int v = 0; v < g->vertices; v++) {
198        if (!visited[v] && in_degree[v] == 0) {
199            visited[v] = true;
200            result[idx] = v;
201
202            /* 인접 정점의 진입 차수 감소 */
203            AdjNode* node = g->adj[v];
204            while (node) {
205                in_degree[node->vertex]--;
206                node = node->next;
207            }
208
209            all_topological_sorts_util(g, visited, in_degree, result, idx + 1, count);
210
211            /* 복원 */
212            visited[v] = false;
213            node = g->adj[v];
214            while (node) {
215                in_degree[node->vertex]++;
216                node = node->next;
217            }
218
219            found = true;
220        }
221    }
222
223    if (!found && idx == g->vertices) {
224        (*count)++;
225        printf("      ");
226        for (int i = 0; i < g->vertices; i++)
227            printf("%d ", result[i]);
228        printf("\n");
229    }
230}
231
232int all_topological_sorts(Graph* g) {
233    bool* visited = calloc(g->vertices, sizeof(bool));
234    int* in_degree = calloc(g->vertices, sizeof(int));
235    int* result = malloc(g->vertices * sizeof(int));
236    int count = 0;
237
238    /* 진입 차수 계산 */
239    for (int v = 0; v < g->vertices; v++) {
240        AdjNode* node = g->adj[v];
241        while (node) {
242            in_degree[node->vertex]++;
243            node = node->next;
244        }
245    }
246
247    all_topological_sorts_util(g, visited, in_degree, result, 0, &count);
248
249    free(visited);
250    free(in_degree);
251    free(result);
252    return count;
253}
254
255/* =============================================================================
256 * 6. 실전: 과목 이수 순서
257 * ============================================================================= */
258
259bool can_finish_courses(int num_courses, int prerequisites[][2], int num_prereqs) {
260    Graph* g = graph_create(num_courses);
261
262    for (int i = 0; i < num_prereqs; i++) {
263        graph_add_edge(g, prerequisites[i][1], prerequisites[i][0]);
264    }
265
266    bool has_cycle;
267    int* result = kahn_topological_sort(g, &has_cycle);
268
269    free(result);
270    graph_free(g);
271
272    return !has_cycle;
273}
274
275int* find_course_order(int num_courses, int prerequisites[][2], int num_prereqs,
276                       int* order_size) {
277    Graph* g = graph_create(num_courses);
278
279    for (int i = 0; i < num_prereqs; i++) {
280        graph_add_edge(g, prerequisites[i][1], prerequisites[i][0]);
281    }
282
283    bool has_cycle;
284    int* result = kahn_topological_sort(g, &has_cycle);
285
286    graph_free(g);
287
288    if (has_cycle) {
289        free(result);
290        *order_size = 0;
291        return NULL;
292    }
293
294    *order_size = num_courses;
295    return result;
296}
297
298/* =============================================================================
299 * 7. 실전: 작업 스케줄링
300 * ============================================================================= */
301
302int* task_scheduling(int num_tasks, int dependencies[][2], int num_deps,
303                     int task_times[], int* completion_times) {
304    Graph* g = graph_create(num_tasks);
305
306    for (int i = 0; i < num_deps; i++) {
307        graph_add_edge(g, dependencies[i][0], dependencies[i][1]);
308    }
309
310    bool has_cycle;
311    int* order = kahn_topological_sort(g, &has_cycle);
312
313    if (has_cycle) {
314        graph_free(g);
315        free(order);
316        return NULL;
317    }
318
319    /* 최단 완료 시간 계산 */
320    for (int i = 0; i < num_tasks; i++)
321        completion_times[i] = task_times[i];
322
323    for (int i = 0; i < num_tasks; i++) {
324        int v = order[i];
325        AdjNode* node = g->adj[v];
326        while (node) {
327            int new_time = completion_times[v] + task_times[node->vertex];
328            if (new_time > completion_times[node->vertex])
329                completion_times[node->vertex] = new_time;
330            node = node->next;
331        }
332    }
333
334    graph_free(g);
335    return order;
336}
337
338/* =============================================================================
339 * 테스트
340 * ============================================================================= */
341
342void print_array(int arr[], int n) {
343    for (int i = 0; i < n; i++)
344        printf("%d ", arr[i]);
345}
346
347int main(void) {
348    printf("============================================================\n");
349    printf("위상 정렬 (Topological Sort) 예제\n");
350    printf("============================================================\n");
351
352    /* 1. Kahn 알고리즘 */
353    printf("\n[1] Kahn 알고리즘 (BFS)\n");
354    Graph* g1 = graph_create(6);
355    graph_add_edge(g1, 5, 2);
356    graph_add_edge(g1, 5, 0);
357    graph_add_edge(g1, 4, 0);
358    graph_add_edge(g1, 4, 1);
359    graph_add_edge(g1, 2, 3);
360    graph_add_edge(g1, 3, 1);
361
362    bool has_cycle;
363    int* result = kahn_topological_sort(g1, &has_cycle);
364    printf("    그래프: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1\n");
365    printf("    위상 정렬: ");
366    if (!has_cycle) print_array(result, 6);
367    printf("\n");
368    free(result);
369
370    /* 2. DFS 기반 */
371    printf("\n[2] DFS 기반 위상 정렬\n");
372    result = dfs_topological_sort(g1);
373    printf("    위상 정렬: ");
374    print_array(result, 6);
375    printf("\n");
376    free(result);
377
378    /* 3. 사이클 탐지 */
379    printf("\n[3] 사이클 탐지\n");
380    Graph* g2 = graph_create(3);
381    graph_add_edge(g2, 0, 1);
382    graph_add_edge(g2, 1, 2);
383    graph_add_edge(g2, 2, 0);  /* 사이클 */
384
385    result = dfs_topological_with_cycle(g2, &has_cycle);
386    printf("    그래프 0→1→2→0 (사이클): %s\n",
387           has_cycle ? "사이클 발견" : "DAG");
388    if (result) free(result);
389    graph_free(g2);
390
391    /* 4. 모든 위상 정렬 */
392    printf("\n[4] 모든 위상 정렬\n");
393    Graph* g3 = graph_create(4);
394    graph_add_edge(g3, 0, 1);
395    graph_add_edge(g3, 0, 2);
396    graph_add_edge(g3, 1, 3);
397    graph_add_edge(g3, 2, 3);
398
399    printf("    그래프: 0→1, 0→2, 1→3, 2→3\n");
400    printf("    모든 순서:\n");
401    int count = all_topological_sorts(g3);
402    printf("    총 %d개\n", count);
403    graph_free(g3);
404
405    /* 5. 과목 이수 */
406    printf("\n[5] 과목 이수 순서\n");
407    int prereqs[][2] = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
408    int order_size;
409    int* course_order = find_course_order(4, prereqs, 4, &order_size);
410
411    printf("    과목: 0, 1, 2, 3\n");
412    printf("    선수: 1←0, 2←0, 3←1, 3←2\n");
413    if (course_order) {
414        printf("    이수 순서: ");
415        print_array(course_order, order_size);
416        printf("\n");
417        free(course_order);
418    }
419
420    /* 6. 작업 스케줄링 */
421    printf("\n[6] 작업 스케줄링\n");
422    int deps[][2] = {{0, 1}, {0, 2}, {1, 3}, {2, 3}};
423    int times[] = {2, 3, 4, 1};  /* 각 작업 소요 시간 */
424    int completion[4];
425
426    int* task_order = task_scheduling(4, deps, 4, times, completion);
427    printf("    작업 시간: [2, 3, 4, 1]\n");
428    printf("    의존성: 0→1, 0→2, 1→3, 2→3\n");
429    if (task_order) {
430        printf("    완료 시간: ");
431        for (int i = 0; i < 4; i++)
432            printf("%d ", completion[i]);
433        printf("\n");
434        free(task_order);
435    }
436
437    graph_free(g1);
438
439    /* 7. 알고리즘 비교 */
440    printf("\n[7] 알고리즘 비교\n");
441    printf("    | 방법      | 시간복잡도 | 특징                  |\n");
442    printf("    |-----------|------------|------------------------|\n");
443    printf("    | Kahn(BFS) | O(V + E)   | 사이클 탐지 용이      |\n");
444    printf("    | DFS       | O(V + E)   | 구현 간단             |\n");
445    printf("    | 모든 정렬 | O(V! * E)  | 모든 경우 열거        |\n");
446
447    printf("\n============================================================\n");
448
449    return 0;
450}