[C] 위상정렬(Topology Sort) 개념 및 정리

위상정렬

위상정렬(Topology Sort)은 순서가 정해져있는 작업을 차례로 수행할 때,

순서를 결정해주기 위해 사용하는 알고리즘이다

 

위상정렬에 대한 이해를 위해 아래의 그래프를 참고해 보자.

아래의 그래 프는 작업의 순서를 그래프로 나타낸 것이다.

이 그래프에는 부분 순서 관계가 있다.

1번 작업을 하기 위해서는 2번 작업을 먼저 완수해야 한다.

7번 작업을 진행하기 위해서는 3번, 또는 6번 또는 8번 작업을 완료해야 한다

 

위상정렬 그래프

 

이때 작업의 순서는 2, 1, 3, 4, 7과 2, 5, 4, 6, 7과 같은 두 가지 계열로 나누어 있음을 알 수 있다.

1번 작업과 5번 작업은 계열이 다르므로 어떤 작업을 먼저 수행해도 상관없다.

이와 같이 전체 그래프의 모든 노드가 아닌 일부 노드에 대해서 선후 관계를 가지는 경우,

이를 부분 순서 관계 (partial order)라고 한다.

 

이러한 부분 순서 관계에 대해 먼저 진행할 작업부터 나중에 진행할 작업까지

일렬로 나열하는 것을 topological sort(위상정렬)이라고 한다.

일부 교재에서는 linearization이라는 용어로 소개되어 있다.

 

위상정렬을 위해서는 먼저 그래프가 directed graph(방향성 그래프)이어야 하며, 사이클이 없어야(DAG; Directed Acyclic Graph) 한다.

위상정렬 알고리즘을 씀으로써,

• 현재 그래프가 위상정렬이 가능한지
• 위상 정렬의 결과는 무엇인지

해결책을 알 수 있다.

 

큐(Queue)를 이용한 방식은 다음과 같다.

1. 진입차수(노드를 가리키는 수)가 0인 정점을 큐에 삽입한다
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다
4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복한다.
   (모든 원소를 방문하기 전에 큐가 빈다면 ? 사이클이 존재
   모든 원소를 방문했다면 ? 큐에서 꺼낸 순서가 위상정렬의 결과)

 

---

C 코드

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 15

typedef struct Queue {
    int front, rear;
    int *data;
}Queue;

int size, inDegree[MAX_SIZE];
int node[MAX_SIZE][MAX_SIZE];

void EnQ(Queue * q, int data) {
    if(q->front == (q->rear + 1)) //FullQ
    {
        puts("Queue is Full");
        return;
    }
    else
    {
        q->rear = q->rear + 1;
        q->data[q->rear] = data;
    }
    return;
}
int DeQ(Queue * q) {
    if(q->front == q->rear) //EmptyQ
    {
        puts("Queue is Empty");
        return;
    }
    else
    {
        q->front = q->front + 1;
        return q->data[q->front];
    }
}

void topologySort() {
    int result[MAX_SIZE];
    Queue q;
    q.front = 0;
    q.rear = 0;
    q.data = malloc(sizeof(int)*MAX_SIZE);

    // 진입 차수가 0인 노드를 큐에 삽입
    for(int i = 1 ; i <= size ; i++) {
        if(inDegree[i] == 0) EnQ(&q, i);
    }

    // n개의 노드 방문
    for(int i = 1 ; i <= size ; i++) {
        if(q.front == q.rear) {
            printf("사이클이 발생했습니다.\n");
            return;
        }

        int x = DeQ(&q);
        int cnt = 0;
        result[i] = x;

        // 노드 x의 간선 제거 & inDegree로 EnQ
        for(int y = 1 ; y <= size ; y++)
            if(node[x][y] == 1) {
                node[x][y] = 0;
                if(--inDegree[y] == 0)
                    EnQ(&q, y);
            }
    }

    for(int i = 1 ; i <= size ; i++)
        printf("%d ", result[i]);
}

int main(){
    size = 8;

    node[1][3] = 1;
    inDegree[3]++;
    node[2][1] = 1;
    inDegree[1]++;
    node[2][5] = 1;
    inDegree[5]++;
    node[3][4] = 1;
    inDegree[4]++;
    node[3][7] = 1;
    inDegree[7]++;
    node[5][4] = 1;
    inDegree[4]++;
    node[5][6] = 1;
    inDegree[6]++;
    node[6][8] = 1;
    inDegree[8]++;
    node[8][7] = 1;
    inDegree[7]++;

    topologySort();
}