위상 정렬(Topology sort)

위상 정렬은 순서가 정해져 있는 작업을 차례로 수행해야할 때 그 순서를 결정해주기 위해 사용하는 알고리즘이다.

대학생의 졸업 과정

 

위와 같은 경우 필요한 절차를 순서대로 밟아야 가능한 경우이며 이럴 때 사용되는 정렬이 위상 정렬이다.

 

위상 정렬 : 대학생 되기 -> 교수님 컨펌 -> 주제 선정 -> 개발하기 -> 졸작 완성 -> 졸작 전시 -> 졸업

 

사이클이 형성된 그래프

 

▷위상 정렬은 시작점을 알아야하기 때문에 위와 같이 사이클이 형성된 그래프에는 위상 정렬을 적용할 수 없다.

 

대학생의 졸업 과정을 번호를 부여하여 그래프로 나타내면

 

 

위상 정렬을 구현하는데 벡터와 큐를 사용하였다.

차수를 나타내는 배열을 선언하여 차수가 0인 것을 우선 전부 큐에 넣고 각 노드마다 인접 노드를 방문하며 차수를 1씩 감소시키며 큐가 빌 때까지 반복문을 사용하였다.

(반복문이 끝나기 전에 큐가 비어버리면 사이클이 형성된 것으로 간주한다.)

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
#define MAX 10

int n;
int Degree[MAX];
vector<int> a[10];



void topologySort() {
	int result[MAX];
	queue <int> q;
	for (int i = 1; i <= n; i++) {
		if (Degree[i] == 0) q.push(i);

	}
	for(int i=1; i<=n; i++){
		int x = q.front();
		q.pop();
		result[i] = x;
		for (int i = 0; i < a[x].size(); i++) {
			int y = a[x][i];
			if (--Degree[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);
	Degree[2]++;
	a[1].push_back(5);
	Degree[5]++;
	a[2].push_back(3);
	Degree[3]++;
	a[3].push_back(4);
	Degree[4]++;
	a[4].push_back(6);
	Degree[6]++;
	a[5].push_back(6);
	Degree[6]++;
	a[6].push_back(7);
	Degree[7]++;

	topologySort();

	return 0;
}

위상 정렬의 시간 복잡도는 O(V+E)이다.