위상 정렬 (Topological Sorting)

 위상 정렬은 순서가 정해진 일들에 대해서 그 순서를 위배하지 않고 일들의 처리 순서를 만드는 방법을 만드는 알고리즘이다. 대표적으로 선수 과목을 예로 들 수 있다. C 과목을 들으려면 B를 들어야 하고, B 과목을 들으려면 A 과목을 들어야 한다고 하자. 그러면 수강 순서는 A -> B -> C 가 될 것이다. 이 순서를 만드는 것이 위상 정렬이다.

 위상 정렬은 DAG (Directed Acyclic Graph) 에서만 성립한다. 즉, 유향 그래프여야 하며, 사이클이 없어야 한다. 무향 그래프의 경우 A -> B 와 B -> A 가 모두 가능하여 선수 과목이라는 조건에 모순이다. 또한 C를 듣기 위해서 B를 듣고, B를 듣기 위해서는 A를 듣는데, 이 때 A를 듣기 위해서 C를 들어야 한다면 이 또한 모순이다.

 

 위상 정렬은 아주 간단하게 DFS 를 이용해서 수행할 수 있다. DFS 를 수행하고 DFS가 종료할 때, 자신을 result 배열에 추가하면 끝이다. C++로 구현한 코드는 다음과 같다.

vector<int> edges[MAX + 1];
vector<int> result;
bool visited[MAX + 1];

void dfs(int start)
{
	visited[start] = true;

	for (int i = 0; i < edges[start].size(); i++)
	{
		int next = edges[start][i];

		if (!visited[next])
		{
			dfs(next);
		}
	}

	result.push_back(start);
}

vector<int> topologicalSort()
{
	for (int i = 1; i <= MAX; i++)
	{
		if (!visited[i])
		{
			dfs(i);
		}
	}

	reverse(result.begin(), result.end());

	return result;
}

 모든 정점에 대한 dfs가 종료되면 result 벡터에는 위상 정렬된 정점들이 역순으로 되어 있을 것이다. 이는 dfs 함수가 종료할 때 result에 자신을 추가하여 맨 처음 시작해야 하는 정점이 가장 마지막에 들어가기 때문이다. 이를 reverse 함수를 통해 역순으로 바꾸면 위상 정렬이 된다.

 

 DFS를 이용한 위상 정렬은 그래프를 어떻게 구현했느냐에 따라 시간 복잡도가 달라질 수 있다. 만약 인접 리스트로 구현했다면 O(|V| + |E|) 시간이 걸리고, 인접 행렬로 구현했다면 O(|V|^2) 이 걸릴 것이다.

 

 

 

참고

- https://ko.wikipedia.org/wiki/%EC%9C%84%EC%83%81%EC%A0%95%EB%A0%AC