위상 정렬 알고리즘(Topology Sort)

  위상 정렬은 '순서가 정해져있는 작업'을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다. 순서가 정해져있는 작업의 대표적인 예시는 다음과 같다.

 

  그래프의 흐름은 사실 '조건'으로 해석할 수 있다. 위와 같이 여러개의 순서가 정해져있을 때 조건에 부합하는 일직선의 순서를 찾아보자.

 

  위상 정렬 : 1 -> 5 -> 2 -> 3-> 4 -> 6-> 7

 

  위와 같이 정렬을 하면 순서대로 작업을 수행했을 때 성공적으로 '7'까지 갈 수 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 이것은 사이클이 발생하지 않는 방향 그래프라는 의미이다. 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다.

 

  위상정렬 알고리즘은 두가지 해결책을 낸다는 특징이 있다. ① 현재 그래프는 위상정렬이 가능한지 ② 위상 정렬이 가능하다면 그 결과는 무엇인지이다. 이러한 위상 정렬을 수행하는 알고리즘으로는 크게 두가지 존재한다.

 

  하나는 스택을 이용한 방식이고, 다른 하나는 큐를 이용한 방식이다. 일반적으로 큐를 많이 사용한다.

 

1. 진입차수가 0인 정점을 큐에 삽입합니다.

2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거합니다.

3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입합니다.

4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복합니다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼내 순서가 위상 정렬의 결과입니다.

 

정 점	1	2	3	4	5	6	7
진입차수	0	1	1	1	1	2	1

 

#include <iostream>
#include <vector>
#include <queue>
#define MAX 10

using namespace std;

int n, inDegree[MAX];
vector<int> a[MAX];

void topologySort() {
	int result[MAX];
	queue<int> q;
	// 진입 차수가 0인 노드를 큐에 삽입.
	for(int i = 1; i <= n; i++) {
		if(inDegree[i] == 0)
			q.push(i);
	}
	// ★위상 정렬이 완전히 수행되려면 정확히 N개의 노드를 방문한다.
	for(int i = 1; i <= n; i++) {
		// n개를 방문하기 전에 큐가 빈다면 사이클이 발생한 것이다.
		if(q.empty()) {
			printf("사이클이 발생");
			return;
		}
		int x = q.front();
		q.pop();
		
		result[i] = x;
		for(int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			// 새롭게 진입차수가 0이 된 정점을 큐에 삽입.
			if(--inDegree[y] == 0) {
				q.push(y);
			}
		}
	}
	for(int i = 1; i <= n; i++) {
		printf("%d ", result[i]);
	}
}

int main() {
	n = 7;
	a[1].push_back(2);
	inDegree[2]++;
	a[1].push_back(5);
	inDegree[5]++;
	a[2].push_back(3);
	inDegree[3]++;
	a[3].push_back(4);
	inDegree[4]++;
	a[4].push_back(6);
	inDegree[6]++;
	a[5].push_back(6);
	inDegree[6]++;
	a[6].push_back(7);
	inDegree[7]++;
	
	topologySort();
}

 

1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7

 

  위상정렬의 시간 복잡도는 O(V + E)이다. 즉 정점의 갯수 + 간선의 갯수만큼 소요되므로 매우 빠른 알고리즘 중 하나이다.