위상정렬(Topology Sort)

위상 정렬(Topology Sort) 는 순서가 정해져있는 작업을 차례로 수행할 때 순서를 결정해주기 위해 사용되는 알고리즘입니다. 예시를 바로 볼까요.

다음과 같이 할 일 루틴이 있다고 합시다. 청소나 블로그 작성은 어느것을 먼저 수행하든지 상관이 없지만 점심은 강의를 복습하고 나서야 할 수 있습니다. 이처럼 한 단계를 수행하기 전에 해야하는, 즉 화살표의 개수(조건)를 '진입 차수' 라고 합니다. 이러한 조건들에 부합하는 일직선이 순서를 찾는것이 위상정렬입니다. 

 

출근 -> 청소 -> 블로그 작성 -> 강의듣기 -> 강의 복습 -> 점심먹기

 

위와 같이 정렬을 수행할 수 있습니다. 그리고 다양한 답이 존재합니다. 그렇기 때문에 더욱 매력적인 알고리즘이라고 할 수 있습니다. 또 위상정렬을 DAG(Directed Acyclic Graph)에만 적용이 가능한데요. 이는 방향성이 있고 사이클이 존재하지 않는다는 말입니다. 사이클이 존재하면 위상 정렬을 수행할 수 없기 때문입니다. 

 

아래와 같이 그래프가 만들어졌다고 생각합시다.

이 그래프에 위상정렬할 수 있을까요? 위상정렬은 시작점이 존재해야하는데(모든 일엔 시작이 있으니깐요) 위와 같은 사이클 그래프에서는 시작점을 찾을 수가 없습니다. 이제 숫자로 표현을 해서 정렬 과정을 조금 더 쉽게 확인해 보겠습니다.

 

위상 정렬 알고리즘은 두가지 해결책을 냅니다.

 

1. 현재 그래프는 위상 정렬이 가능한지

2. 위상 정렬이 가능하다면 그 결과는 무엇인지

 

이러한 위상 정렬을 수행하는 알고리즘은 큐나 스택을 사용할 수 있는데 여기서는 큐로 사용해보겠습니다. 

 

① 진입 차수가 0인 정점을 큐에 삽입

② 큐에서 원소를 꺼내 연결된 모든 간선 제거

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입 

④ 큐가 빌때까지 2번~3번 과정 반복, 모든 원소를 방문하기 전 큐가 빈다면 사이클이 존재하는 겁니다. 모든 원소를 방문 했다면 큐에서 꺼내 순서가 정렬의 결과입니다. 

 

 

이제 위상정렬을 시작해보겠습니다.

① 진입차수가 0인 1을 큐에 삽입합니다. 

② 큐에서 원소 1을 꺼내 연결된 모든 간선 제거

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입

표가 다음과 같이 갱신이 됩니다. 이 2,3번 과정을 반복해줍시다. 

진입차수가 0이된 2, 3을 큐에 삽입해줍니다.

② 큐에서 원소를 꺼내 연결된 모든 간선 제거, 원소 2를 꺼내주겠습니다. 

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입

② 큐에서 원소를 꺼내 연결된 모든 간선 제거, 원소 3를 꺼내주겠습니다. 

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입, 여기서는 추가할 게 없습니다.

② 큐에서 원소를 꺼내 연결된 모든 간선 제거, 원소 4를 꺼내주겠습니다. 

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입, 6을 삽입해줍니다. 

② 큐에서 원소를 꺼내 연결된 모든 간선 제거, 원소 6을 꺼내주겠습니다. 

③ 간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입, 5를 삽입해줍니다.

② 큐에서 원소를 꺼내 연결된 모든 간선 제거, 원소 5을 꺼내주겠습니다. 

 

이렇게 위상 정렬이 마무리가 되었습니다. 순서는 위에서 보시는 것과 같이 1 2 3 4 6 5 입니다. 

 

 

 

---

추가로 이해를 돕기 위해 사이클이 있는 그래프를 들고 왔습니다.

 

시작 점이자 진입 차수가 0인 1을 큐에 넣어줍니다.

큐에서 1을 빼주면서 간선을 다 제거 해줍니다.

 

아...? 큐가 비었는데 방문하지 않은 진입 차수가 0인 노드가 없습니다. 이렇기 때문에 위상 정렬에는 사이클 있는 그래프가 있어서는 안됩니다. 

 

이제 C++ 로 구현을 해보도록 하겠습니다. 

// Topology Sort.cpp : 이 파일에는 'main' 함수가 포함됩니다. 거기서 프로그램 실행이 시작되고 종료됩니다.
//

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10

using namespace std;

int n, inDegree[MAX];
vector<int> a[MAX];
void topoloySort() {
    int result[MAX];
    queue<int> q;

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

    //위상정렬이 완전히 수행되려면 모든 노드를 방문해야함
    for (int i = 1; i <= n;i++) {
        //n개를 방문하기 전에 큐가 빈다면 사이클이 발생
        if (q.empty()) {
            printf("cycle\n");
            return;
        }
        int x = q.front();
        q.pop();
        result[i] = x; //큐에서 꺼낸 순서가 위상 정렬을 한 순서
        for (int i = 0; i < a[x].size();i++) {
            int y = a[x][i];
            //새롭게 진입차수가 0인 된 정점을 큐에 삽입
            if (--inDegree[y] == 0) {
                q.push(y);
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        printf("%d ", result[i]);
    }
}

int main()
{
    n = 6;
    a[1].push_back(2);
    inDegree[2]++;
    a[1].push_back(3);
    inDegree[3]++;
    a[2].push_back(4);
    inDegree[4]++;
    a[4].push_back(6);
    inDegree[6]++;
    a[6].push_back(5);
    inDegree[5]++;
    a[3].push_back(5);
    inDegree[5];

    topoloySort();
}

저희가 생각했던 값과 동일하게 나온다는 것을 볼 수 있습니다.

 

오늘은 위상 정렬에 대해 알아보았습니다. 수고하셨습니다.