Clean Code hochulshin.com

Algorithm - Topological Sort

2016-02-25

Topological Sort는 dependency를 가진 것들을 처리할 때 어떤 순서로 처리해야 하는지를 알아내기 위한 그래프 알고리즘이다. 예를 들어, a -> b, b -> c, a -> c라는 의존 관계가 있다면 a -> b -> c라는 순서로 처리되어야만 한다. 보통 의존성이 있는 작업들이 있을 때 순서를 구하거나, 소프트웨어의 각 모듈간 의존성을 고려한 설치 순서등을 정할 때 사용된다.

알고리즘

Topological sort는 의존성을 가진 것들의 처리 순서를 다루는 것이므로 방향성 그래프에 적용된다. 다음과 같은 어프로치를 활용한다.

  • 다른 vertex들이 의존하지 않는 vertex부터 하나 씩 지워나간다.

예를 들어 a -> b, b -> c, a -> c라는 의존 관계에서 c를 지우고, b를 지우고, a를 지우는 식으로 진행하는 것이다. 이 어프로치를 구현하기 위한 알고리즘은 다음과 같다.

  • 그래프내의 모든 vertex들을 방문할 때까지
  • DFS로 vertex를 순회한다.
  • 한 vertex를 기준으로 볼 때 자신의 adjacent vertex들을 모두 방문하거나, 혹은 adjacent vertex가 없어서 더 이상 자신에게 의존하는 vertex가 남아 있지 않으면 이때 자신을 스택에 넣는다.
  • 모든 vertex를 방문했다면 스택에서 하나씩 pop을 한다. pop된 아이템들의 순서가 바로 topological_sort된 순서이다.

간단히 pseudo 코드로 표현하면 다음과 같다.

dfs(graph, vertex id, visited[], stack){
	해당 vertex 방문한 것으로 check
	모든 인접 vertex 순회하며 {
		if(인접 vertext 방문한 적이 없다면){
			dfs(graph, 인접 vertex id, visited, stack);
		}
	}
	stack vertex 푸쉬한다.
}
topological_sort(graph){
	자료 구조 초기화: graph, visited[], stack
	graph내의 모든 vertex 대해 {
		dfs(graph, vertex id, visited, stack)
		방문한 vertex 숫자가 graph vertex 숫자와 일치하면 loop 멈춤
	}
	stack에서 하나씩 push하면서 출력한다. 
}

코드

위의 pseudo code를 실제 코드로 작성한 것은 다음과 같다. set 자료 구조를 사용해 visited 여부를 체크하고, vector를 stack로 사용했다.

#include <iostream>
#include <set>
#include <vector>
using namespace std;
void dfs(vector<vector<bool> > &G, int index, set<int> &Visited, vector<int> &Stack){
	Visited.insert(index); //방문한 것으로 Check
	for (int i = 0; i<G.size(); i++){
		if (i == index) continue;	//자기 자신은 Skip
		if (G[index][i]){			//연결된 Vertex가 있다면 (edge가 true)
			auto it = Visited.find(i);
			if (it == Visited.end()){		//방문했던 Vertex인지 확인해서 하지 않았다면 
				dfs(G, i, Visited, Stack);	//방문한다. 
			}
		}
	}
	Stack.push_back(index);				//더 이상 방문할 것이 없다면 V에 넣는다.(즉, 자신에게 의존적인 Vertex들을 모두 처리한 후에 자신을 처리)
}
vector<int> topological_sort(vector<vector<bool> > &G){
	set<int> Visited;
	vector<int> Stack;
	for (int i = 0; i<G.size(); i++){	//각 Vertex에서 시작해서 Graph를 dfs로 travesal한다. 
		dfs(G, i, Visited, Stack);
		if (Visited.size() == G.size()){
			return Stack;
		}
	}
	return Stack;
}
int main(){
	/* create graph */
	vector<vector<bool> > G(5, vector<bool>(5, false));
	G[0][4]  = true;
	G[0][2]  = true;
	G[2][3]  = true;
	G[1][4]  = true;
	G[2][1]  = true;
	vector<int> stack = topological_sort(G);
	while (stack.size()){
		cout << stack.back() << " ";
		stack.pop_back();
	}
	return 0;
}

Comments