위상 정렬(topological sorting)

1. 정의

단방향 그래프에서 A->B의 관계가 있을 경우, 반드시 A를 먼저 출력 후, B를 출력한다.
A->B<-C의 경우, A 또는 C를 먼저 출력하고 B를 출력한다. 위상 정렬을 하는 경우 A와 C의 출력 순서는 무엇이 먼저든 상관 없다. 그렇기 때문에 위상 정렬을 실행하면 항상 유니크한 값을 얻지는 않는다. 위상 정렬을 수행하기 위해선 반드시 그래프의 순환이 존재하지 않아야 한다.

2. 용도

- Build System

IDE(통합 개발 환경)을 사용해서 개발을 진행할 때, 프로젝트 내에 서로 의존성을 가지고 있는 다양한 라이브러리들이 존재하면 IDE는 위상 정렬을 통해 어떤 라이브러리가 먼저 설치되어야 하는지 알려줄 수 있다.

- Advanced-Packaging Tool(apt-get)

리눅스 사용자에게 익숙한 apt-get은 특정 소프트웨어를 설치하고 제거해야 하는지 위상 정렬을 통해 판단하게 된다.

- Task Scheduling, Pre-requisite problems ...

3. 예시

위의 그래프를 위상 정렬했을 경우 "5 4 2 3 1 0"이라는 결과값을 가질 수 있다. 하지만 "4 5 2 3 1 0"이라는 결과값 역시 가질 수 있다. 위상 정렬을 실행하기 위한 첫 번째 시작점이 차수가 0이면 되기 때문이다.(a vertex with no incoming edges.)

4. 알고리즘

DFS를 살짝 변경해서 그래프의 위상 정렬을 수행할 수 있다. DFS에서는 처음 방문한 버텍스를 출력하고 DFS의 재귀적 호출을 통해 인접한 버텍스들을 방문해가며 값을 출력했다.

위상 정렬은 임시 스택(temporary stack)을 이용하게 된다. DFS에서는 처음 방문한 버텍스의 값을 즉시 출력했지만, 위상 정렬에서는 값을 스택에 저장하게 된다. 그리고 재귀적 호출을 하여 모든 인접한 버텍스들의 값들을 스택에 저장하게 된다. 마지막으로 스택에 저장된 값들을 출력하면 위상 정렬된 값들을 얻게 된다.

5. 구현

스택을 이용한 구현(DFS 응용)

#include <bits/stdc++.h>
using namespace std;
const int MX = 100001;
vector<int> V[MX];
bool vis[MX];
int v, e; // vertices, edges
stack<int> temp_stack; // temporary stack

void topo(int vertex) {
    vis[vertex] = 1;
    for(int i=0; i<V[vertex].size(); i++) {
        if(vis[V[vertex][i]]) continue;
        topo(V[vertex][i]);
    }
    temp_stack.push(vertex);
}

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> v >> e;
    for(int i=0; i<e; i++) {
        int x, y;
        cin >> x >> y;
        V[x].push_back(y);
    }

    cout << "Print Adjacency list\n";
    for(int i=0; i<v; i++) {
        cout << i << " -> ";
        for(int j=0; j<V[i].size(); j++) {
            cout << V[i][j] << ' ';
        }
        cout << '\n';
    }
    // topological sorting 
    for(int i=0; i<v; i++) {
        if(vis[i]) continue;
        topo(i);
    }
    
    while(!temp_stack.empty()) {
        cout << temp_stack.top() << ' ';
        temp_stack.pop();
    }
}

큐를 이용한 구현(진입 차수 이용)

#include <bits/stdc++.h>
using namespace std;
const int MX = 100001;
vector<int> V[MX];
int degree[MX];
int result[MX];
int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    queue<int> Q;
    for(int i=0; i<m; i++) {
        int x, y;
        cin >> x >> y;
        V[x].push_back(y);
        degree[y]++;
    }
    for(int i=1; i<=n; i++) {
        if(degree[i] == 0) Q.push(i);
    }
    
    for(int i=1; i<=n; i++) {
        int cur = Q.front(); Q.pop();
        result[i] = cur;

        for(int j=0; j<V[cur].size(); j++) {
            int nxt = V[cur][j];
            degree[nxt]--;
            if(degree[nxt]==0) Q.push(nxt);
        }
    }
    for(int i=1; i<=n; i++) {
        cout << result[i] << ' ';
    }

    // vector<int> ans;
    // while(!Q.empty()) {
    //     int cur = Q.front(); Q.pop();
    //     ans.push_back(cur);
    //     for(int i=0; i<V[cur].size(); i++) {
    //         int nxt = V[cur][i];
    //         degree[nxt]--;
    //         if(degree[nxt]==0) Q.push(nxt);
    //     }
    // }

    // for(int i=0; i<ans.size(); i++) {
    //     cout << ans[i] << ' ';
    // }
}

6. 참고 사이트

https://practice.geeksforgeeks.org/problems/topological-sort/1