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

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

 

위상 정렬은 방향성이 있는 유향 그래프에서 순서가 정해져있는 정점들의 순서를 거스르지 않으면서 모든 정점을 나열하는 알고리즘입니다. 위상 정렬의 대표적인 예시는 다음과 같습니다.

예를 들어 컴퓨터공학과에서 알고리즘 과목을 수강하고자 할 때 해당 과목을 수강하기 위한 선수 과목들이 존재합니다. 즉, 알고리즘을 수강하기 위해선 자료구조를 먼저 수강해야 하며 C프로그래밍을 수강하기 위해서는 먼저 이산수학을 수강해야 할 것입니다. 

 

순서가 존재하는 유향그래프에서 위 예시를 위상 정렬하면 다음과 같은 순서가 나타납니다.

이산수학 -> 프로그래밍 원리 -> C프로그래밍 -> 자료구조 -> 알고리즘

 

위상 정렬을 통해 올바른 수강순서를 찾아낼 수 있습니다. 이처럼 선후 관계가 명확한 그래프 구조에서 그 관계에 따라 정렬하는 알고리즘이 위상 정렬입니다. 위상 정렬의 순서는 구조에 따라 여러 종류가 나타날 수 있으며 그래프 내에 반드시 사이클이 존재해서는 안됩니다. 사이클이 존재하는 그래프에서는 시작 지점을 찾을 수 없으므로 위상 정렬이 불가능합니다.

 

알고리즘 원리

위 유향그래프에서 모든 정점들은 진입 차수를 가지고 있습니다. 진입 차수는 정점에 들어오는 간선 수를 의미합니다. 그림에서 정점 1의 진입 차수는 0이며 정점 6의 진입 차수는 2입니다.

 

위상 정렬에는 큐 자료구조가 사용되며 기본적인 알고리즘은 다음과 같습니다.

(1) 진입 차수가 0인 정점을 큐에 넣는다.

(2) 큐에서 정점을 꺼내고 그 정점의 진출 간선을 제거한다.

(3) 제거 후 새로 진입 차수가 0이 되는 정점이 있으면 그것을 큐에 넣는다.

(4) 큐가 공백 상태가 될 때까지 (2)와 (3)을 반복한다.

 

위상 정렬의 결과는 큐에서 정점을 꺼낼 때 꺼내진 순서가 정렬의 순서가 됩니다. 만약 모든 정점을 방문하기 전에 큐가 공백 상태가 되버린다면 그 그래프는 사이클이 존재하는 순환 그래프입니다.

먼저 진입 차수가 0인 정점 1을 큐에 넣습니다.

큐에서 정점 1을 꺼내고 진출 간선을 제거하면 정점 2와 5의 진입 차수가 0이 되므로 큐에 넣습니다.

큐에서 정점 2를 꺼내고 진출 간선을 제거하면 정점 3의 진입 차수가 0이 되므로 큐에 넣습니다.

큐에서 정점 5를 꺼내고 진출 간선을 제거하면 정점 6의 진입 차수가 0이 되므로 큐에 넣습니다.

큐에서 정점 3을 꺼내고 진출 간선을 제거하고 새롭게 진입 차수가 0이 되는 정점이 없으므로 넘어갑니다.

큐에서 정점 6을 꺼내고 진출 간선을 제거하면 정점 4의 진입 차수가 0이 되므로 큐에 넣습니다.

큐에서 정점 4를 꺼내고 진출 간선을 제거하면 정점 7의 진입 차수가 0이 되므로 큐에 넣습니다.

큐에서 정점 7을 꺼냅니다. 이로써 큐에서 꺼내진 순서에 따라 1 -> 2 -> 5 -> 3 -> 6 -> 4 -> 7 로 위상 정렬됩니다.

 

알고리즘 구현

// Algorithm Analysis
// 위상 정렬 (Topology Sort)

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

using namespace std;

int n = 7;
int 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 j = a[x][i];
			if (--inDegree[j] == 0) {
				q.push(j);
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		cout << result[i] << " ";
	}
}
int main() {
	a[1].push_back(2);
	inDegree[2]++;
	a[1].push_back(5);
	inDegree[5]++;
	a[2].push_back(3);
	inDegree[3]++;
	a[2].push_back(6);
	inDegree[6]++;
	a[3].push_back(4);
	inDegree[4]++;
	a[4].push_back(7);
	inDegree[7]++;
	a[5].push_back(6);
	inDegree[6]++;
	a[6].push_back(4);
	inDegree[4]++;

	topologySort();
}
// 1 2 5 3 6 4 7

 

시간 복잡도 : O(V + E)

위상 정렬의 시간 복잡도는 O(V + E)이며 정점 수 + 간선 수만큼의 빠른 시간 복잡도를 가집니다.

 

 

 

* 나동빈님 블로그를 참고하여 개인적으로 재작성한 글입니다.