123. Topological Sorting

위상 정렬(Topological Sorting)은 DAG의 정점을 재배열하는 알고리즘으로, 정점을 재배열했을 때 간선의 방향은 모두 동일해야 한다. 모든 DAG는 위상 정렬이 가능하며, DAG가 아닌 모든 그래프는 위상 정렬이 불가능하다.

 

위상 정렬을 하는 방법은 다음과 같다.

    1. 아직 선택하지 않은 정점들 중 진입 차수가 $0$인 정점 하나를 선택하고 정렬된 정점 목록의 맨 뒤에 추가한다.

    2. 선택한 정점 및 그 정점과 연결된 간선들을 그래프에서 제거한다.

    3. 모든 정점이 선택될 때까지 과정 1, 2를 반복한다.

 

아래의 그래프에서 위상 정렬을 실행하면 다음과 같다.

진입 차수가 $0$인 정점은 $\text{D}$ 하나이므로 정점 $\text{D}$ 및 정점 $\text{D}$와 연결된 간선들을 그래프에서 제거한다.

D

정점 $\text{D}$와 연결된 간선들이 제거되면서 정점 $\text{F}$의 진입 차수가 $0$이 되었으므로 두 번째로 정점 $\text{F}$ 및 정점 $\text{F}$와 연결된 간선들을 그래프에서 제거한다.

D - F

다음으로 정점 $\text{E}$와 $\text{C}$를 차례로 선택한다.

D - F - E

D - F - E - C

같은 방법으로 정점 $\text{H}$, $\text{I}$, $\text{A}$, $\text{G}$, $\text{B}$를 차례로 선택하면 위상 정렬이 끝난다. 최종 정렬 결과는 $\text{D}$ - $\text{F}$ - $\text{E}$ - $\text{C}$ - $\text{H}$ - $\text{I}$ - $\text{A}$ - $\text{G}$ - $\text{B}$가 된다. 정점들을 위상 정렬한 순서대로 나타내면 다음과 같다.

구현 방법은 크게 두 가지가 있는데, 첫 번째는 위에서 설명한 방식을 그대로 사용하는 것이다. 단 진입 차수가 $0$인 정점을 매 반복마다 일일히 찾으면 시간복잡도가 $O(n^2)$이 되므로 큐를 사용하여 시간복잡도를 $\Theta(n+m)$으로 줄인다. 큐에는 진입 차수가 $0$인 정점들이 들어가며, 위상 정렬 결과는 벡터 $v$에 저장된다. ($n$: 정점의 개수, $m$: 간선의 개수)

#import<bits/stdc++.h>
using namespace std;
int ind[100005]; // ind는 indegree의 약자로 사용됨
vector<int>v, e[100005];
queue<int>Q;
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        int[y]++;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!ind[i])Q.push(i);
    }
    for(; Q.size(); Q.pop())
    {
        x = Q.front();
        v.push_back(x);
        for(auto &p: e[x])
        {
            if(!--ind[p])Q.push(p);
        }
    }
}

만약 그래프에 사이클이 존재한다면 코드의 실행이 끝난 다음 $v$에 일부 정점이 들어가지 않게 된다. 이것으로 사이클의 존재 여부를 판별할 수 있다.

 

두 번째 방법은 DFS를 이용하는 것이다. 진입 차수가 $0$인 정점들에서 DFS를 실행하고 정점의 방문이 끝날 때마다 정점을 $v$에 추가하면 위상 정렬의 역순으로 정점이 저장된다. 따라서 DFS의 실행이 끝난 다음 $v$를 뒤집으면 위상 정렬이 완료된다.

#import<bits/stdc++.h>
using namespace std;
int ind[100005], vi[100005];
vector<int>v, e[100005];
void dfs(int node)
{
    if(vi[node])return;
    vi[node] = 1;
    for(auto &p: e[node])dfs(p);
    v.push_back(node);
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        ind[y]++;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!ind[i])dfs(i);
    }
    reverse(v.begin(), v.end());
}

다소 비직관적이지만 진입 차수가 $0$인 정점들을 체크하지 않고 그냥 일일히 DFS를 돌리는 방법도 가능하다.

#import<bits/stdc++.h>
using namespace std;
int vi[100005];
vector<int>v, e[100005];
void dfs(int node)
{
    if(vi[node])return;
    vi[node] = 1;
    for(auto &p: e[node])dfs(p);
    v.push_back(node);
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)dfs(i);
    reverse(v.begin(), v.end());
}

DFS를 이용하여 구현할 경우 사이클의 존재 여부를 저 코드만으로는 판별할 수 없기 때문에 그래프에 사이클이 존재하는지 모르는 경우 DFS 트리에 역방향 간선이 존재하는지를 체크해야 한다.

#import<bits/stdc++.h>
using namespace std;
int cycle, vi1[100005], vi2[100005];
vector<int>v, e[100005];
void dfs(int node)
{
    if(vi1[node])
    {
        if(!vi2[node])cycle = 1;
        return;
    }
    vi1[node] = 1;
    for(auto &p: e[node])dfs(p);
    v.push_back(node);
    vi2[node] = 1;
}
int main()
{
    int m, n, x, y;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)dfs(i);
    reverse(v.begin(), v.end());
}

정점 $v$의 방문을 시작할 때 $\text{vi}_1[v]$가 True로, $v$의 방문이 끝날 때 $\text{vi}_2[v]$가 True로 변한다. $\text{vi}_1[v]$가 True, $\text{vi}_2[v]$가 False인 정점을 방문할 경우 역방향 간선이 존재하는 것이다. 이를 이용해서 사이클의 존재 여부를 확인할 수 있다.

 

[연습문제]

 

BOJ 2252. 줄 세우기 (Gold III)

기본적인 위상 정렬 문제이다.

 

BOJ 2623. 음악프로그램 (Gold II)

각 PD가 정한 순서에 따라 먼저 출연하는 가수에서 나중에 출연하는 가수 쪽으로 간선을 만들고 위상 정렬을 한다.

 

BOJ 1948. 임계경로 (Platinum V)

위상 정렬을 이용하여 출발 도시에서 각각의 도시까지 이동하는 데 걸리는 최소 시간 $a_i$, 각각의 도시에서 도착 도시까지 이동하는 데 걸리는 최소 시간 $b_i$, 출발 도시에서 도착 도시까지 이동하는 데 걸리는 최소 시간 $t$를 구한다. 다음으로 각각의 도로를 확인하는데, $u$번 도시에서 $v$번 도시로 $w$분 만에 갈 수 있는 도로가 있을 때 $a_u + w + b_v = t$인 경우 이 도로는 답에 포함된다.

 

→ solved.ac tag: topological_sorting