Topological sort

* 위상 정렬(Topological sort)

  의존성이 있는 작업들이 주어질 때, 이들을 어떤 순서로 수행해야 하는지 계산할 때 필요하다. 이런 DAG의 정점을 배열하는 것을 위상 정렬이라 한다.

  구현 방식은 두 가지 방식이 있다. DFS와 BFS.

1. DFS

  BFS와 다르게 indegree 배열이 필요가 없다. 또한 나중엔 반드시 reversing process가 필요하다.

코드 :

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

#include<vector> vector<int> visit, order; void dfs(int here){     visit[here] = 1;     for(int there = 0; there < adj.size(); ++there)         if(adj[here][there] && !visit[there])             dfs(there);     order.push_back(here); }   void main(){     //... preprocess           for(int i=0;i<adj.size();i++)         if(!visit[i])             dfs(i);     reverse(order.begin(), order.end());           //... skip }

2. BFS

  indegree 배열에 진입 간선이 없는지에 대해 확인하고 queue에 삽입함으로써 순서대로 정렬할 수 있다.

코드 :

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include<queue> void main(){     //... preprocess           queue<int> q;     for(i=0;i<adj.size();i++)         if(indegree[i] == 0)             q.push(i);     while(!q.empty()){         printf("%d ",q.front());         int u = q.front(); q.pop();         for(i=0;i<adj.size();i++){             if(adj[u][i]){                 indegree[i] -= 1;                 if(indegree[i] == 0)                     q.push(i);             }         }     }           //... skip }