MENU
  1. ホーム
  2. C 언어
  3. C 언어로 위상 정렬 구현하기: 알고리즘과 코드 예제

C 언어로 위상 정렬 구현하기: 알고리즘과 코드 예제

C 언어

C 언어에서 위상 정렬은 방향성 비순환 그래프(Directed Acyclic Graph, DAG)의 노드를 특정 순서로 나열하는 기법입니다. 위상 정렬은 프로젝트 관리, 컴파일러의 의존성 분석, 작업 스케줄링 등에서 중요한 역할을 합니다. 본 기사에서는 위상 정렬의 기본 개념부터 알고리즘, C 언어로의 구현, 그리고 실용적인 응용 사례까지 다루어, 이를 명확히 이해하고 실전에 적용할 수 있도록 안내합니다.

목차

위상 정렬이란 무엇인가


위상 정렬(Topological Sort)은 방향성 비순환 그래프(DAG)의 노드들을 그들의 의존성을 반영한 선형 순서로 정렬하는 알고리즘입니다.

기본 개념


DAG는 사이클이 없는 방향성 그래프로, 작업 간의 의존 관계를 나타내는 데 적합합니다. 위상 정렬은 이러한 의존 관계를 기반으로 작업 수행 순서를 정하는 데 사용됩니다.

활용 가능한 상황

  • 작업 스케줄링: 서로 의존 관계가 있는 작업들을 올바른 순서로 수행해야 하는 경우
  • 컴파일러 설계: 소스 파일 간의 의존성을 분석해 컴파일 순서를 결정
  • 프로젝트 관리: 작업과 의존 관계를 그래프로 표현하여 효율적으로 관리

위상 정렬은 DAG에만 적용 가능하며, 그래프에 사이클이 존재할 경우 정렬이 불가능합니다.

위상 정렬의 핵심 알고리즘


위상 정렬을 구현하는 두 가지 주요 알고리즘은 Kahn의 알고리즘과 DFS(Depth-First Search) 기반 방법입니다. 이 두 알고리즘은 각기 다른 방식으로 그래프의 정렬 순서를 도출합니다.

Kahn의 알고리즘


Kahn의 알고리즘은 그래프의 진입 차수(In-degree)를 기반으로 위상 정렬을 수행합니다.

  1. 모든 노드의 진입 차수를 계산합니다.
  2. 진입 차수가 0인 노드를 큐에 삽입합니다.
  3. 큐에서 노드를 하나씩 제거하면서 해당 노드의 이웃 노드들의 진입 차수를 감소시킵니다.
  4. 진입 차수가 0이 된 노드를 다시 큐에 삽입합니다.
  5. 큐가 빌 때까지 위 과정을 반복하며, 제거된 순서가 위상 정렬의 결과가 됩니다.

이 알고리즘은 그래프에서 사이클이 없는 경우에만 작동하며, 시간 복잡도는 (O(V + E))입니다.

DFS 기반 알고리즘


DFS를 이용한 위상 정렬은 그래프의 방문 여부를 기록하며 재귀적으로 순서를 정합니다.

  1. 방문하지 않은 노드부터 DFS를 시작합니다.
  2. DFS로 그래프를 탐색하며, 더 이상 진행할 수 없는 노드를 스택에 삽입합니다.
  3. 모든 노드에 대해 DFS가 완료되면, 스택의 역순으로 정렬된 결과를 얻습니다.

이 방법 역시 시간 복잡도는 (O(V + E))로, Kahn의 알고리즘과 동일합니다.

알고리즘 선택

  • Kahn의 알고리즘: 직관적이고 순서를 큐에 저장하며 확인하기 쉬운 방식이 필요할 때 적합
  • DFS 기반 알고리즘: 재귀적 접근이 더 자연스러운 상황이나 특정 구조에 적합

이 두 가지 알고리즘은 각각의 장단점이 있으므로, 문제의 특성과 요구 사항에 따라 선택하여 사용하면 됩니다.

위상 정렬을 위한 그래프 표현


C 언어에서 위상 정렬을 구현하려면 그래프를 적절히 표현하는 데이터 구조가 필요합니다. 일반적으로 인접 리스트(Adjacency List)와 인접 행렬(Adjacency Matrix) 두 가지 방법이 사용됩니다.

인접 리스트


인접 리스트는 각 노드와 연결된 이웃 노드들의 목록을 저장하는 방식으로, 메모리 효율적이고 간결합니다.

  • 구조: 배열과 연결 리스트를 사용하여 그래프를 표현
  • 특징: 노드 수가 많고 간선이 적은 경우(희소 그래프)에 적합

예제 코드:

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
} Graph;

인접 행렬


인접 행렬은 노드 간의 연결 상태를 2차원 배열로 표현합니다.

  • 구조: (N \times N) 크기의 배열을 사용하여 노드 간의 간선을 나타냄
  • 특징: 그래프가 밀집되어 있는 경우(간선 수가 많을 때) 적합

예제 코드:

#define MAX_VERTICES 100
int adjacencyMatrix[MAX_VERTICES][MAX_VERTICES];

데이터 구조 선택 기준

  1. 그래프 크기와 밀도:
  • 희소 그래프: 인접 리스트 권장
  • 밀집 그래프: 인접 행렬 권장
  1. 알고리즘 효율성:
  • 인접 리스트는 간선에 대해 순회하는 작업에서 효율적
  • 인접 행렬은 특정 간선의 존재 여부를 빠르게 확인 가능

그래프 입력 처리


그래프를 구현할 때 파일이나 사용자 입력을 통해 노드와 간선을 정의하는 기능을 포함시켜야 합니다.

  • 인접 리스트 입력 예제:
void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}
  • 인접 행렬 입력 예제:
void addEdgeMatrix(int matrix[][MAX_VERTICES], int src, int dest) {
    matrix[src][dest] = 1;
}

적절한 데이터 구조를 선택하면 위상 정렬의 구현이 더 효율적이고 직관적이 됩니다.

위상 정렬 구현 코드


C 언어로 위상 정렬을 구현하기 위해 Kahn의 알고리즘과 DFS 기반 알고리즘의 코드 예제를 제시합니다.

Kahn의 알고리즘 구현


다음은 인접 리스트를 기반으로 작성된 Kahn의 알고리즘 구현 코드입니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* inDegree;
} Graph;

Graph* createGraph(int vertices);
void addEdge(Graph* graph, int src, int dest);
void topologicalSort(Graph* graph);

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);

    printf("Kahn's Algorithm Topological Sort:\n");
    topologicalSort(graph);

    return 0;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->inDegree = calloc(vertices, sizeof(int));

    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
    graph->inDegree[dest]++;
}

void topologicalSort(Graph* graph) {
    int* queue = malloc(graph->numVertices * sizeof(int));
    int front = 0, rear = 0;

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->inDegree[i] == 0)
            queue[rear++] = i;
    }

    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        Node* temp = graph->adjLists[current];
        while (temp) {
            graph->inDegree[temp->vertex]--;
            if (graph->inDegree[temp->vertex] == 0)
                queue[rear++] = temp->vertex;
            temp = temp->next;
        }
    }

    free(queue);
}

DFS 기반 알고리즘 구현


다음은 재귀를 활용한 DFS 기반 위상 정렬 구현 코드입니다.

#include <stdio.h>
#include <stdlib.h>

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    Node** adjLists;
    int* visited;
} Graph;

Graph* createGraph(int vertices);
void addEdge(Graph* graph, int src, int dest);
void topologicalSortDFS(Graph* graph);
void dfs(Graph* graph, int vertex, int* stack, int* stackIndex);

int main() {
    Graph* graph = createGraph(6);
    addEdge(graph, 5, 2);
    addEdge(graph, 5, 0);
    addEdge(graph, 4, 0);
    addEdge(graph, 4, 1);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 1);

    printf("DFS Topological Sort:\n");
    topologicalSortDFS(graph);

    return 0;
}

Graph* createGraph(int vertices) {
    Graph* graph = malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = malloc(vertices * sizeof(Node*));
    graph->visited = calloc(vertices, sizeof(int));

    for (int i = 0; i < vertices; i++)
        graph->adjLists[i] = NULL;

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;
}

void topologicalSortDFS(Graph* graph) {
    int* stack = malloc(graph->numVertices * sizeof(int));
    int stackIndex = -1;

    for (int i = 0; i < graph->numVertices; i++) {
        if (!graph->visited[i])
            dfs(graph, i, stack, &stackIndex);
    }

    while (stackIndex >= 0)
        printf("%d ", stack[stackIndex--]);

    free(stack);
}

void dfs(Graph* graph, int vertex, int* stack, int* stackIndex) {
    graph->visited[vertex] = 1;

    Node* temp = graph->adjLists[vertex];
    while (temp) {
        if (!graph->visited[temp->vertex])
            dfs(graph, temp->vertex, stack, stackIndex);
        temp = temp->next;
    }

    stack[++(*stackIndex)] = vertex;
}

위의 두 알고리즘은 각각 다른 상황에서 활용할 수 있으며, 프로젝트 요구 사항에 맞는 방식을 선택하면 됩니다.

위상 정렬의 주요 응용 사례


위상 정렬은 다양한 실제 문제를 해결하는 데 활용됩니다. 이를 통해 위상 정렬의 중요성과 실용성을 이해할 수 있습니다.

1. 작업 스케줄링


위상 정렬은 여러 작업 간의 의존 관계를 고려하여 작업의 순서를 정할 때 사용됩니다.

  • 예: 건설 프로젝트에서 특정 작업이 완료된 후 다른 작업이 시작되어야 하는 경우
  • 구현: 작업을 노드로, 의존 관계를 간선으로 표현한 DAG를 구성하고 위상 정렬을 수행

구체적 예시


건물 공사 과정에서 다음과 같은 작업이 있다고 가정합니다.

  • 작업 A: 기반 공사
  • 작업 B: 기둥 세우기 (작업 A 완료 후)
  • 작업 C: 지붕 설치 (작업 B 완료 후)
    이때 DAG를 구성하여 위상 정렬을 수행하면 작업 순서가 도출됩니다.

2. 컴파일러 설계


컴파일러는 여러 소스 파일 간의 의존성을 분석하여 컴파일 순서를 결정합니다.

  • 소스 파일 간의 포함 관계(#include)를 DAG로 표현
  • 위상 정렬로 올바른 컴파일 순서 결정

3. 패키지 관리


소프트웨어 패키지 관리자(Apt, npm 등)에서 설치 순서를 정할 때 위상 정렬이 사용됩니다.

  • 특정 패키지가 다른 패키지에 의존할 경우, 의존 패키지를 먼저 설치하도록 순서를 결정
  • DAG를 기반으로 한 위상 정렬로 충돌 없는 설치 순서 도출

4. 학습 과정 설계


교육 커리큘럼에서 선수 과목이 존재하는 경우, 위상 정렬로 학습 순서를 정할 수 있습니다.

  • 예: 과목 A(기초) → 과목 B(응용) → 과목 C(전문)
  • DAG에서 각 과목을 노드로 표현하고 위상 정렬로 순서 도출

5. 게임 개발


게임 내 이벤트 시스템에서 특정 이벤트가 다른 이벤트에 의존할 때, 실행 순서를 정하는 데 위상 정렬이 활용됩니다.

  • 예: 퀘스트 A 완료 후 퀘스트 B가 시작되도록 설계

위와 같은 사례들은 위상 정렬이 다양한 분야에서 필수적인 도구로 사용되고 있음을 보여줍니다. 이를 통해 문제 해결 능력을 향상시키고 효율적인 시스템 설계를 도울 수 있습니다.

자주 발생하는 문제 및 디버깅 팁


위상 정렬을 구현하거나 사용하는 과정에서 발생할 수 있는 일반적인 문제와 이를 해결하기 위한 디버깅 팁을 제시합니다.

1. 입력 그래프의 사이클

  • 문제: 위상 정렬은 방향성 비순환 그래프(DAG)에만 적용 가능합니다. 입력 그래프에 사이클이 있으면 정렬이 불가능합니다.
  • 해결 방법:
  • Kahn의 알고리즘: 모든 노드를 처리하지 못한 경우, 그래프에 사이클이 있다는 의미입니다.
  • DFS 기반 알고리즘: DFS 실행 중 노드를 다시 방문하게 되면 사이클이 존재합니다.
  • 사이클을 감지하는 코드 추가:
    c if (visited[neighbor] && onStack[neighbor]) { printf("Cycle detected!\n"); return; }

2. 그래프 표현 오류

  • 문제: 그래프를 잘못 표현하거나 간선을 잘못 추가하는 경우, 위상 정렬이 제대로 수행되지 않습니다.
  • 해결 방법:
  • 그래프를 출력하여 노드와 간선의 연결 상태를 확인합니다.
  • 인접 리스트나 행렬 데이터를 디버그용으로 출력하는 함수 작성:
    c void printGraph(Graph* graph) { for (int i = 0; i < graph->numVertices; i++) { printf("Vertex %d:", i); Node* temp = graph->adjLists[i]; while (temp) { printf(" %d", temp->vertex); temp = temp->next; } printf("\n"); } }

3. 잘못된 초기화

  • 문제: 노드 방문 여부나 진입 차수 배열 초기화를 잘못하면 알고리즘이 예상대로 작동하지 않을 수 있습니다.
  • 해결 방법:
  • 초기화를 확인하고, 모든 배열을 적절히 초기화합니다.
    c memset(visited, 0, sizeof(int) * numVertices); memset(inDegree, 0, sizeof(int) * numVertices);

4. 메모리 누수

  • 문제: 동적 메모리를 사용하는 인접 리스트 구현에서 메모리 누수가 발생할 수 있습니다.
  • 해결 방법:
  • 노드와 리스트를 모두 해제하는 함수 작성:
    c void freeGraph(Graph* graph) { for (int i = 0; i < graph->numVertices; i++) { Node* temp = graph->adjLists[i]; while (temp) { Node* next = temp->next; free(temp); temp = next; } } free(graph->adjLists); free(graph->inDegree); free(graph); }

5. 출력 순서 오류

  • 문제: 정렬된 결과가 의도한 순서와 다를 수 있습니다.
  • 해결 방법:
  • 입력 데이터와 출력 결과를 비교하여 간선 순서를 확인합니다.
  • 데이터 구조(큐나 스택) 동작을 디버깅 로그로 기록합니다.

디버깅 요령

  • 작은 그래프(노드 4~5개)를 테스트 케이스로 사용해 알고리즘의 동작을 검증합니다.
  • 로그를 추가해 알고리즘의 각 단계를 확인합니다.
  printf("Processing node: %d\n", current);
  printf("Queue state: ...\n");
  • 다양한 입력(희소 그래프, 밀집 그래프, 사이클 포함 그래프)을 테스트하여 견고성을 확인합니다.

이러한 디버깅 팁은 위상 정렬을 구현할 때 발생하는 문제를 효과적으로 해결하고 안정적인 프로그램을 만드는 데 도움을 줄 것입니다.

요약


위상 정렬은 방향성 비순환 그래프(DAG)의 노드들을 의존 관계에 따라 정렬하는 알고리즘으로, 작업 스케줄링, 컴파일러 설계, 패키지 관리 등 다양한 분야에서 활용됩니다. 본 기사에서는 위상 정렬의 개념, Kahn의 알고리즘과 DFS 기반 구현, 그래프 표현 방식, 주요 응용 사례 및 디버깅 팁을 다루었습니다. 이를 통해 위상 정렬의 이론과 실용적 활용 방법을 명확히 이해할 수 있습니다.

C 언어
C언어 알고리즘 위상 정렬 자료구조
목차