위상 정렬(Topological Sort)

[flflds0811]

위상 정렬 (Topological Sort)

DAG(directed acyclic graph) 에서 정점을 나열하는데, 이 때, 나중에 나온 정점에서 먼저나온 정점으로 간선이 없게 나열하는 것을 위상 정렬이라한다.

일반적으로 정렬을 하는 이유 와 마찬가지로 위상정렬을 하는 이유는 graph에서 위상정렬을 함으로 인해서 어떤 이점을 얻기 위해서이다.

구현 방법은 간단하다. 자신으로 들어오는 간선의 수 indegree 를 이용하면 된다. indegree 간선의 수를 확인하고 indegree 가 0 인 정점만 다음 순서의 후보가 될 수 있다. 선택된 정점은 자신의 간선을 확인하여 연결된 정점의 indegree를 감소해 주면 된다. queue를 이용하여 O(V+E) 로 구현이 가능하다.

다음과 같은 몇 가지 상황에 사용할 수 있다.

1. 선행되는 작업이 수행되어야 다음 작업을 할 수 있을 때 위상정렬을 한 후 해당 정렬된 순서대로 작업을 처리한다면 선행작업이 완료되었음을 보장할 수 있다. (만약, 현재 수행될 수 있는 작업들 중에서 우선순위가 있다면, queue 대신 priority_queue를 사용할 수 있다.)

2. graph에서 1:N 최단경로를 구할 때 DAG인 경우 위상정렬을 수행해두면 모든 점으로의 거리를 INF 로 설정해두고 각 정점을 방문하면서, 현재까지의 최단경로 + 지금 정점으로 갈 수 있는 다음 정점 으로 다음 정점의 최단경로를 갱신함으로 인해서 1:N 최단경로를 O(V+E)로 구할 수 있다.

3. Directed Graph에서 사이클 유무를 알 수 있다. (위상정렬이 실패한다면 사이클이 존재한다는 의미)

[flflds0811]

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
using namespace std;
int indeg[1010];
int topol[1010];
vector<vector<int> > vt;
int v,e,u,w;
int main() {
    scanf("%d%d",&v,&e);
    vt.resize(v);
    while(e--) {
        scanf("%d%d",&u,&w);
        vt[u].push_back(w);
        indeg[w]++;
    }
    queue<int> q;
    for(int i=0;i<v;i++) 
      if(indeg[i]==0) q.push(i);
    for(int i=0;i<v;i++) {
        if(q.empty()) {
            return 0; //실패
        }
        int cv = q.front();
        q.pop();
        topol[i] = cv;
        for(int j=0;j<vt[i].size();j++)
          if(--indeg[vt[i][j]] == 0) q.push(vt[i][j]);
    }
    return 0;
}