Topological sort

* 위상 정렬(Topological sort)

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

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

1. DFS

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

코드 :

#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에 삽입함으로써 순서대로 정렬할 수 있다.

코드 :

#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
}