위상 정렬 (Topology Sort)

위상 정렬

• 순서가 정해져 있는 작업을 차례대로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘
• DAG (Directed Acyclic Graph: 사이클이 발생하지 않는 방향 그래프)에만 적용 가능
• 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음
• 위상 정렬은 시작점이 존재해야함. 사이클 그래프에서는 시작점 찾을 수 없음. 불가능
• 위상 정령은 두 가지의 해결책 보여줌
  1. 현재 그래프는 위상 정렬이 가능?
  2. 가능하다면, 그 결과는?

구현 방법

1. 진입 차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선 제거
3. 간선 제거 이후에 진입차수가 0이된 정점을 큐에 삽입
4. 큐가 빌 때 까지 2~3번 과정 반복

• 모든 원소를 방문하기 전에 큐가 빈다면, 사이클이 존재하는 것
• 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬의 결과

 

관련 문제

www.acmicpc.net/problem/2252

2252번: 줄 세우기

코드 구현

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> v[32001];
int n, m;
int inDegree[32001];
int result[32001];
void topologySort()
{
    queue<int> q;
    for (int i = 1; i <= n; i++)
    {
        if (inDegree[i] == 0)
            q.push(i);
    }

    // 정렬이 완전히 수행되려면 정확히 n개의 노드 방문
    for (int i = 1; i <= n; i++)
    {
        int x = q.front();
        q.pop();
        result[i] = x;

        for (int i = 0; i < v[x].size(); i++)
        {
            int y = v[x][i];
            if (--inDegree[y] == 0)
                q.push(y);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        cout << result[i] << ' ';
    }
}
int main()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        inDegree[b]++;
    }
    topologySort();
}