위상 정렬 (Topological Sort)

위상 정렬이란 유향 그래프에서 정해진 순서를 위배하지 않도록 나열하는 것입니다.
예를 들면 전략 게임에서의 빌드 오더나 선수강과목을 예로 들 수 있습니다.
전략 게임의 빌드 오더에서 A를 짓지 않으면 B를 지을 수 없고, B를 짓지 않으면 C를 지을 수 없다와 같은 규칙이 있을 수 있고, 선수강과목은 자료구조 과목을 듣지 않으면 알고리즘 과목을 수강할 수 없다는 규칙이 있을 수 있습니다.
이러한 순서에 따라서 나열하는 것이 바로 위상 정렬입니다.
만약에 이런 규칙에 순환이 생긴다면 순환이 생긴 그 무엇도 나열할 수 없기 때문에 DAG(directed acylic graph)에서만 위상 정렬이 가능합니다.

구현 방법에 대해서 설명을 하자면, 먼저 그래프를 구성할 때 간선의 의미는 A->B 라면, A를 방문해야 B를 방문할 수 있다는 것입니다.
다시 말해서 B를 하기 전에 A를 해야 한다는 것이죠.
따라서 내부 간선(Incoming Edge)이 존재한다는 것은 자기 자신을 방문하기 전에 방문해야 할 정점들이 남아있다는 것이고, 현재 수행 불가하다는 것을 의미합니다.

따라서 InDegree가 0인 정점들만 방문이 가능한 정점이고, 나머지들은 자신의 차례가 오기를 기다리는 정점들이 됩니다.
정점을 방문하였을 때 자신과 연결된 간선들을 지워나가는 방식을 사용하면 DAG에서 모든 정점을 방문할 수 있습니다.
예를 들어 다음의 그림을 보면 A를 방문하게 된 후 A와 연결된 간선 A->B라는 간선(B의 내부 간선)을 지우면 B의 InDegree(파란 박스)가 1에서 0으로 바뀌게 되고, B는 방문 가능한 정점이 됩니다.
따라서 위상정렬 결과는 A B가 됩니다.

이러한 알고리즘의 구현 방법에는 두 가지가 있습니다.

첫 번째 방법은 Kahn의 알고리즘입니다.
처음에 내부 간선이 0인 정점들을 List의 뒤에 넣어주고, List가 비어있을 때까지 이러한 정점들을 방문하며 연결된 간선들을 모두 제거하고, 지워지는 간선과 연결된 정점이 방문 가능한 상태가 되었는지 확인하여 방문 가능하다면 List의 뒤에 넣어주는 방식을 반복하는 방법이 있습니다.

두 번째 방법은 깊이 우선 탐색을 이용한 방법입니다.
모든 정점을 반복문을 돌면서 내부 간선이 0인 정점인지 확인하여 DFS를 돌립니다.
돌다가 더 이상 이동할 수 있는 간선이 없을 경우 해당 정점을 List의 앞에 넣어줍니다.
이러한 과정을 반복하면 List에 위상정렬 결과가 들어가게 됩니다.

다음은 C++로 나타낸 코드입니다.

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

vector<vector<int> > edge;
vector<int> ind;
int N, M;
int u, v;
int main() {
    cin >> N >> M;
    edge.resize(N + 1);
    ind.resize(N + 1);
    for (int i = 0; i < M; i++) {
        cin >> u >> v;
        edge[u].push_back(v);
        ind[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= N; i++) {
        if (ind[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        cout << here << ' ';
        for (int i = 0; i < edge[here].size(); i++) {
            int there = edge[here][i];
            ind[there]--;
            if (ind[there] == 0) {
                q.push(there);
            }
        }
    }
    return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    static int n;
    static int m;
    static int s;

    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        ArrayList<Integer>[] adj_list = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            adj_list[i] = new ArrayList<>();
        }
        int ind[] = new int[n + 1];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            adj_list[u].add(v);
            ind[v]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= n; i++) {
            if (ind[i] == 0) {
                q.add(i);
            }
        }
        while (!q.isEmpty()) {
            int here = q.remove();
            System.out.print(String.valueOf(here) + ' ');
            for (int i = 0; i < adj_list[here].size(); i++) {
                int there = adj_list[here].get(i);
                ind[there]--;
                if (ind[there] == 0) {
                    q.add(there);
                }
            }
        }
    }
}