위상 정렬

위상 정렬(Topological sorting)은 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것을 말합니다.

 

쉽게 말해서 간선 $u \rightarrow v$가 있다면, 정점 $v$는 무조건 정점 $u$이후에 등장해야 합니다.

 

예를 들어 다음과 같은 유향 그래프에서,

$$\{1, 5, 2, 3, 6, 4\}$$

는 가능한 위상 정렬 중 하나입니다.

 

방향 그래프에 사이클이 존재한다면, 위상 정렬 역시 존재할 수 없습니다.

따라서 그래프는 항상 '사이클 없는 유향그래프'(Directed Acyclic Graph, DAG)여야 합니다.

 

그러면 위상 정렬을 구하는 알고리즘에 대해 알아봅시다.

 

https://www.acmicpc.net/problem/2252

2252번: 줄 세우기

 

1. DFS를 이용한 방법

 

그래프를 DFS로 탐색합시다.

각 정점에서의 탐색이 모두 끝났을 때, 스택에 현재 정점을 추가 합니다.

 

DFS가 모두 완료되고 나면 이 스택안에서 모든 정점은 이 정점에서 연결될 수 있는 모든 정점이 나온 이후에 등장하게 됩니다.

이 스택을 뒤집으면 가능한 위상정렬 중 하나가 됩니다.

 

이 방법을 이용할 때는 그래프에 사이클이 존재해서 위상 정렬이 존재하지 않는 경우에도 무언가 결과가 나오기 때문에, 사이클의 존재 여부를 먼저 확인한 다음 사용해야 합니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
vector <int> graph[32001];
 
bool hasCycle = 0;
int cache[32001];
// 0 : 아직 탐색 안됨, 1 : 탐색 중, 2 : 탐색 완료
 
vector <int> stk; // 스택
void DFS(int v)
{
    cache[v] = 1;
    for (auto nv : graph[v])
    {
        if (cache[nv] == 1) hasCycle = 1;
        // 만약 탐색 중인 정점을 또 만났다면 사이클이 존재한다.
        if (cache[nv] == 0) DFS(nv);
    }
    cache[v] = 2;
    stk.push_back(v);
    // 탐색 완료 후 이 정점을 스택에 추가한다.
}
 
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
    }
 
    for (int i = 1; i <= n; i++)
    {
        if (cache[i] == 0) DFS(i);
    }
 
    if (hasCycle)
    {
        cout << -1;
        return 0;
        // 이 문제에서는 여기에 도달하지 않는다.
    }
 
    reverse(stk.begin(), stk.end());
    // 스택을 뒤집으면 그대로 위상 정렬중 하나가 된다.
 
    for (int i : stk) cout << i << ' ';
}

 

시간복잡도는 일반적인 DFS와 같이 $O(V+E)$입니다.

---

 

https://www.acmicpc.net/problem/1766

1766번: 문제집

 

2. 칸 알고리즘 (Kahn's Algorithm)

 

위와 같이 가능한 위상정렬을 '아무거나' 하나 구할 수도 있지만, 특정한 조건에 맞는 위상정렬을 구해야 한다면 다른 방법을 사용해야 합니다.

 

어떤 정점이 위상 정렬의 첫 원소로 올 수 있다면, 이 정점으로 들어오는 간선(진입 간선)이 없어야 합니다.

 

조건에 따라 정렬되는 우선순위 큐를 하나 준비한 다음, 진입 간선이 0인 정점들을 모두 추가합시다.

그 후, 우선순위 큐의 맨 앞에 있는 정점을 위상 정렬에 추가합시다.

이 정점에 연결된 간선들을 모두 제외했을 때, 진입 간선이 0인 정점이 생긴다면 우선순위 큐에 추가합니다.

 

이 방법으로 특정한 조건에 맞는 위상 정렬을 하나 만들 수 있게 됩니다.

위상정렬이 존재하지 않는 경우도 감지할 수 있습니다.

아직 추가하지 않은 정점이 남아 있는데도 우선순위 큐가 비어있게 된다면 이 그래프에서 위상정렬은 존재하지 않습니다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, m;
vector <int> graph[32001];
int in[32001];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int u, v; cin >> u >> v;
        graph[u].push_back(v);
 
        in[v]++;
        // v의 진입차수를 1 추가한다.
    }
 
    priority_queue <int> pq;
    for (int i = 1; i <= n; i++)
    {
        if (in[i] == 0) pq.push(-i);
        // 진입 간선이 없는 정점들을 pq에 추가한다.
    }
 
    vector <int> ans;
    for (int i = 0; i < n; i++)
    {
        if (pq.empty())
        {
            cout << -1;
            return 0;
            // 큐가 비어있다면 위상 정렬이 존재하지 않는다.
            // 이 문제에서는 여기에 도달하지 않는다.
        }
 
        int v = -pq.top(); pq.pop();
        ans.push_back(v);
 
        for (int nv : graph[v])
        {
            if (--in[nv] == 0) pq.push(-nv);
            // v에 연결된 간선을 모두 제거했을 때 진입 차수가 0이 되는 정점이 있다면 pq에 추가한다.
        }
    }
 
    for (int v : ans) cout << v << ' ';
}

 

시간복잡도를 계산해 봅시다.

일반적인 그래프 탐색에 $O(V+E)$이 시간이 걸리고,

우선순위 큐에 최대 $V$개의 원소가 추가/삭제 됩니다.

따라서 총 시간복잡도는 $O(E+V\log V)$입니다.

---

제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.

 

www.acmicpc.net/group/7712

ANZ1217