[자료구조] 그래프 위상 정렬 알고리즘

 

위상 정렬이란?

순서가 정해져있는 작업을 차례대로 수행해야 할 때 사용하는 알고리즘입니다.

방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열할 수 있습니다.

 

위상 정렬의 특징

위상 정렬의 특징은 다음과 같습니다.

• 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방함. 따라서 다수의 위상 순서가 있을 수 있음
• 위상 정렬 과정에서 선택되는 정점의 순서를 위상 순서(topological order)라고 함
• 만약 진입 차수가 0인 정점이 없다면, 실행 불가능한 프로젝트가 되고 위상 정렬 알고리즘이 중단됨
• 그래프에 사이클이 존재하지 않아야 함

 

위상 정렬의 작동 방식

그래프에 있는 노드들의 진입 차수를 배열에 저장합니다.

그 후, 진입 차수가 0인 노드를 큐/스택에 삽입합니다. 이 때, 둘 중 아무거나 선택해도 상관없습니다. 구현은 스택으로 해보도록 하겠습니다.

간선을 제거한 이후에 진입 차수가 0이 된 노드를 스택에 삽입합니다. 모든 노드가 없어질 때 까지 반복합니다.

주의사항: 모든 노드를 없애기 전 스택이 빈다면 사이클이 돌아서 추가되지 않았다는 뜻입니다. 따라서 위상 정렬이 제대로 되지 않음을 표시해야 합니다.

 

int topo_sort(Graph *g) {
    int i;
    Stack s;
    GraphNode *node;

    int *in_degree = (int *)malloc(g->n *sizeof(int));
    for(i = 0; i < g->n; i++) {
        in_degree[i] = 0;
    }
    for(i = 0; i < g->n; i++) {
        GraphNode *node = g->adj_list[i];
        while(node != NULL) {
            in_degree[node->vertex]++;
            node = node -> link;
        }
    }

    init(&s);
    for(i = 0; i < g->n; i++) {
        if(in_degree[i] == 0) push(&s, i);
    }

    while(!is_empty(&s)) {
        int w = pop(&s);
        printf("정점 %d ->", w);
        node = g->adj_list[w];
        while(node != NULL) {
            int u = node->vertex;
            in_degree[u]--;
            if(in_degree[u] == 0) push(&s, u);
            node = node->link;
        }
    }
    free(in_degree);
    printf("\n");
    return (i == g->n);
}