[C++] 위상 정렬( Topology Sort )

위상 정렬( Topology Sort )이란

위상 정렬이란 주어진 DAG( Directed Acyclic Graph )에서 간선의 방향에 따라 모든 정점을 나열하는 것을 말합니다.

여기서, DAG란 순환 경로가 없는 방향 그래프를 말합니다.

 

그리고, 간선의 방향을 따른다는 뜻은,

정점 A에서 B로 이어지는 간선이 있을 때, A가 B보다 먼저 나열되어야 한다는 뜻입니다.

 

예를 들어, 다음 그래프는 DAG입니다.

 

간단한 Directed Acyclic Graph

 

이때, 위상 정렬을 하면 3, 1, 2가 됩니다.

 

이렇게 정점들을 나열하는 것은, 작업들 중에서 먼저 수행해야 되는 작업 순으로 작업들을 나열하는 과정과 같습니다.

그래서, 위상 정렬은 순환 경로가 있는 그래프에서는 성립되지 않습니다.

먼저 나열해야 하는 정점을 지정할 수 없기 때문입니다. 

 

위상 정렬을 할 수 없는 그래프

 

 

이러한 위상 정렬을 수행하는 과정은 다음과 같습니다.

 

1. indegree가 0인 정점들을 선택해 queue에 넣는다.

    여기서, 정점의 indegree란,

    다른 정점에서 출발하여 그 정점에 연결되는 간선의 개수를 말합니다.

    그리고, DAG는 순환 경로가 없는 방향 그래프이므로 반드시 indegree가 0인 정점이 존재합니다.

 

2. queue에서 정점을 꺼내, 이 정점과 연결된 정점의 간선을 제거한다.

3. indegree가 0이 된 정점들을 queue에 넣는다.

4. 모든 정점을 방문할 때까지 2의 과정을 반복한다.

 

다음 예제로 위의 과정을 따라서 위상 정렬이 수행되는 것을 살펴보겠습니다.

 

 

먼저, indegree가 0인 정점은 1과 5입니다.
queue에 넣습니다.

 

 

1을 queue에서 꺼내, 1과 연결된 간선을 제거합니다.

아직, indegree가 0인 정점은 없습니다.

 

 

 

정점 5를 queue에서 꺼내, 5과 연결된 간선을 제거합니다.

이제, 정점 2의 indegree가 0이 되었으므로, queue에 넣습니다.

 

 

 

정점 2를 queue에서 꺼내, 2와 연결된 간선을 제거합니다.
이제, 정점 3과 6의 indegree가 0이 되었으므로, 모두 queue에 넣습니다.

 

 

 

정점 3을 queue에서 꺼내, 3와 연결된 간선을 제거합니다.
이제, 정점 4의 indegree가 0이 되었으므로, queue에 넣습니다. 

 

 

 

정점 6을 queue에서 꺼내, 6과 연결된 간선을 제거합니다.
이제, 정점 7의 indegree가 0이 되었으므로, queue에 넣습니다.

 

 

 

정점 4를 queue에서 꺼냅니다.

indegree가 0인 정점은 없습니다.

 

 

 

마지막 정점 7을 queue에서 꺼내고, queue가 비워졌습니다.

이렇게 해서 위상 정렬이 끝납니다.

 

위성 정렬 완료

 

 

정점들의 순서는 queue에서 꺼낸 순서가 됩니다.

위의 경우는 1 -> 5 -> 2 -> 3 -> 6 -> 4 -> 7 순으로 정점이 정렬됩니다.

 

참고로, 정점 5도 처음 indegree가 0이었습니다.

따라서, 5 -> 1 -> 2 -> 3  -> 6 -> 4 -> 7 순서로 정렬해도 위상 정렬이 됩니다.

마찬가지로, 정점 3과 6을 queue에 넣는 순서에 따라 정렬의 결과가 달라질 수 있습니다.

이렇듯, 위상 정렬은 단 한 가지의 순서만 존재하는 것은 아닙니다.

 

그리고, queue 대신 stack이나 heap 자료구조를 사용하여 정렬할 수도 있습니다.

중요한 것은 간선의 방향을 따라 정렬이 되는 것입니다.

 

이 과정을 코드로 작성하면 다음과 같습니다.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define SIZE 7

vector<int> graph[SIZE+1];
int indegree[SIZE+1];   // 정점의 indegree
int sorted[SIZE+1]; 	// 정렬된 결과 저장

void Topology_Sort(){

    queue<int> q;

    for( int i = 1; i <= SIZE; i++){
        if ( indegree[i] == 0)  // 정렬을 시작할 정점
            q.push(i);
    }

    int idx = 1;
    while( !q.empty()){
        int vert = q.front();
        q.pop();

        sorted[idx++] = vert;   // 정렬된 순서 기록

        for( int x : graph[vert]){
            indegree[x]--;
            if ( indegree[x] == 0){
                q.push(x);
            }
        }
    }
}

int main(){

    graph[1].push_back(2);
    indegree[2]++;
    
    graph[2].push_back(3);
    indegree[3]++;

    graph[3].push_back(4);
    indegree[4]++;

    graph[3].push_back(7);
    indegree[7]++;

    graph[5].push_back(2);
    indegree[2]++;

    graph[2].push_back(6);
    indegree[6]++;

    graph[6].push_back(7);
    indegree[7]++;
    
    Topology_Sort();

    for(int i = 1; i <= SIZE; i++){
        cout << sorted[i] << " ";
    }

    return 0;
}