그래프의 Vertex를 정렬하는 Topological Sort - Kahn's Algorithm

그래프의 Vertex에는 순서가 있을까?

대학교의 전공 과목에는 선수 과목이라는 것이 존재한다. 특정 과목을 수강하기 위해서는 해당 과목의 선수 과목을 먼저 수강해야 하는 것이다.

이러한 관계를 이용해서, Topological Sort를 이용하면 올바른 수강 순서를 얻어낼 수 있다.

우리는 Vertex의 정렬 기준을 In-degree, Out-degree의 차수로 나타내어 Sorting Algorithm을 정의해볼 수 있다.

 

Topological Sort: Directed(방향이 있는) Graph G에서 모든 Vertex를 정렬한 것.

• Vertex 정렬 기준: 임의의 vertex u, v가 있을 때 edge(u,v)가 존재할 경우 vertex u는 vertex v보다 순서가 앞이다.
• 오직 Cycle이 없는 Directed Graph(DAG)에서만 정의된다(why? 방향성이 없거나 cycle이 생길 경우 무한 루프). 

출처: https://i.imgur.com/Q3MA6dZ.png

위와 같은 그림에서, 그래프의 모든 Vertex를 Topologically하게 정렬할 경우 오른쪽 그림과 같이 [0,6,1,5,4,2,3]의 Vertex Set을 얻을 수 있다.

 

그래프를 정렬하는 Topological Sorting Algorithm 중에서도 Kahn's Algorithm을 알아보자

Kahn's Algorithm: 모든 Vertex를 방문할 때 까지 1️⃣-2️⃣의 과정을 반복한다

1️⃣ In-degree가 0인 Vertex중 임의의 Vertex를 출력

2️⃣ 1에서 출력한 Vertex 및 그 Vertex로부터 향하는 모든 Edge들을 Graph에서 모두 삭제

 

즉, 맨 위의 그림을 예시로 들면

1. In-degree가 0인 Vertex(0, 6)중 임의의 한 vertex인 0을 삭제하면서 출력

2. 0에서 1, 2로 향하는 Edge를 모두 삭제

3. 그 다음으로 In-degree가 0인 Vertex 6 삭제하면서 출력

4. 6에서 1, 5로 향하는 Edge를 모두 삭제

... 반복

 

이러한 Kahn's Algorithm은 Queue를 이용해서 구현할 수 있다(Queue가 빌 때 까지 1️⃣~3️⃣을 반복)

in_degree[0 ... n] : 0~N번 Vertex까지 각 vertex의 현재 in-degree를 저장하는 Array

1️⃣ Vertex 하나를 dequeue하고 출력(해당 vertex를 v라고 가정)

2️⃣ in_degree[i]가 0이 아닌 모든 Vertex i에 대해 edge(v,i)가 존재하면, in_degree[i]의 값을 1 감소

3️⃣ 2번에 의해 in_degree[i]의 값이 0으로 바뀌면 vertex i를 enqueue

 

Topological Sort를 사용하는 BOJ 문제인 줄세우기에서 다음과 같이 활용할 수 있다.

www.acmicpc.net/problem/2252

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int n, m,indeg[32005];
vector<int> graph[32005];
queue<int> q;
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0,a,b; i < m; i++) {
		scanf("%d%d", &a, &b);
		graph[a].push_back(b);
		indeg[b]++;
	}
	for (int i = 1; i <= n; i++)
		if (!indeg[i])q.push(i);

	while (!q.empty()) {
		int cur = q.front(); q.pop();
		printf("%d ", cur);
		for (int i : graph[cur])
			if (indeg[i]) {
				indeg[i]--;
				if (!indeg[i])q.push(i);
			}
	}
	return 0;
}