위상 정렬

위상 정렬(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