[C++] 위상 정렬(Topology Sort)

위상 정렬은 비순환 단방향 그래프에서 순서가 정해져 있는 작업을 차례대로 수행해야 할 때 그 순서를 결정해주는 알고리즘이다. 순서만 맞으면 되기 때문에 정답이 두 개 이상일 수 있다. 단, 사이클이 발생하는 경우 위상 정렬을 수행할 수 없다. 이렇게 사이클이 발생하지 않는 그래프를 DAG(Directed Acyclic Graph)라고 한다. 즉, 위상정렬은 DAG에서만 정의될 수 있다.

​

위상 정렬을 구현하기 위해서 '진입 차수'라는 개념을 알아야 한다. '진입 차수'란 노드로 들어오는 간선의 개수다. 말로 하면 헷갈리니깐 바로 그림으로 알아보자.

위 그림의 경우 진입 차수는 3이다. 노드0으로 들어오는 화살표의 개수가 3이기 때문이다.

위 그림의 경우 진입 차수는 0이다. 노드 0으로 들어오는 화살표가 하나도 없기 때문이다.

​

진입차수의 개념을 이해했다면 위상정렬 알고리즘을 어렵지 않게 이해할 수 있다. 위상정렬 알고리즘은 진입차수가 0인 노드를 출력하고 이와 연결된 간선을 제거하는 방식으로 진행된다.

[ 위상정렬 알고리즘 ]
1. 진입차수가 0인 노드를 큐에 삽입한다.
2. 큐에서 원소를 꺼내 출력하고, 이와 연결된 모든 간선을 제거한다.
3. 큐가 빌때까지 1~2번 과정을 반복한다. 

<주의>
1-2번 과정을 노드의 개수만큼 반복한다. 
그 전에 큐가 비었으면 순환한다는 뜻이므로 불가 메시지를 출력한다.

 

 

이제 그래프에서 직접 위상정렬을 수행해보자.

 

위상정렬을 수행하기 전에, 눈으로 답을 도출해보자. 아래 두 경우 모두 답이 될 수 있다.

0 → 1 → 4 → 2 → 3 → 5 → 6
0 → 4 → 1 → 2 → 3 → 5 → 6  // 위에서 1 → 4 순서만 바뀜

두번째와 세번째의 순서가 다르지만 우선순위에 위배되지 않기 때문에 모두 정답이 될 수 있다. 이제 바로 해보자!!

 

진입차수가 0인 노드가 노드0 밖에 없으므로 큐에 노드0만 삽입해준다.

노드0을 출력하고 노드0과 연결된 간선을 제거해준 뒤에 진입차수를 초기화해준다. 그 결과 두 노드(노드1, 노드4)의 진입차수가 0이 되었다. 이를 모두 큐에 삽입해준다.

노드1을 출력하고 노드1과 연결된 간선을 제거해준 뒤에 진입차수를 초기화해준다. 그 결과 노드2의 진입차수가 0이 되었다. 이를 큐에 삽입해준다.

노드4를 출력하고 노드4와 연결된 간선을 제거해준 뒤 진입차수를 초기화해준다. 그 결과 노드5의 진입차수가 2에서 1로 변경되었다.

노드2를 출력하고 노드2와 연결된 간선을 제거해준 뒤 진입차수를 초기화해준다. 그 결과 노드3의 진입차수가 0이 되었다. 이를 큐에 삽입해준다.

노드3을 출력하고 노드3과 연결된 간선을 제거해준 뒤 진입차수를 초기화해준다. 그 결과 노드5의 진입차수가 0이 되었다. 이를 큐에 삽입해준다.

노드5를 출력하고 노드5와 연결된 간선을 모두 제거해준 뒤 진입차수를 초기화해준다. 그 결과 노드 6의 진입차수가 0이 되었다. 이를 큐에 삽입해준다.

노드6을 출력해준다. 노드6과 연결된 간선은 없으므로 pass한다. 모든 노드를 검사했으므로 종료한다.

​

​

코드는 아래와 같다. 백준 2252번의 정답 코드이기도 하다.

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N; // 노드 수
int M; // 간선 수
int inDgree[32001] = {0, };
vector<vector<int>> graph(32001);

void topology_sort() {
	queue<int> q;

	for (int i = 1; i <= N; i++) {
		if (inDgree[i] == 0)
			q.push(i); // 진입차수가 0인 노드 push
	}

	for (int rep = 0; rep < N; rep++) {
		if (q.empty()) {
			cout << "비순환 그래프입니다" << endl;
			return;
		}

		int from = q.front();
		cout << from << ' ';
		q.pop();
		for (int i = 0; i < graph[from].size(); i++) {
			int to = graph[from][i];
			inDgree[to]--;
			if (inDgree[to] == 0)
				q.push(to);
		}
	}

}

int main() {
	int a, b;

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		graph[a].push_back(b);
		inDgree[b]++;
	}

	topology_sort();

	return 0;
}