위상 정렬(Topology Sort)

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

 

주의할 점은 위상 정렬은 사이클이 발생하지 않는 방향 그래프 즉, DAG(Directed Acyclic Graph)에만 수행이 가능하다.

 

왜냐하면 위상 정렬은 기본적으로 시작점이 존재해야 하는데 사이클 그래프에서는 시작점부터 찾을 수 없기 때문이다.

 

위상 정렬을 수행하는 과정은 아래와 같다.

위상 정렬(Topology Sort) 과정

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

여기서 진입차수는 해당 정점에 들어오는 간선의 수이다. 즉, 정점6은 정점4와 정점5에서 간선이 들어오기 때문에 

 

진입차수가 2이다. 또한, 정점1은 들어오는 간선이 없기 때문에 진입차수는 0이다.

 

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

큐(Queue)

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

간선 제거

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

정점1과 연결된 간선을 제거함으로써 정점2와 정점5의 진입차수는 0으로 갱신된다.

 

(3) 진입차수가 0이 된 정점2와 정점5를 큐에 삽입한다.

(4) 정점2를 꺼내 연결된 모든 간선을 제거한다.

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

 

그 다음 정점3을 큐에 넣어준 뒤 정점5를 큐에서 꺼내 연결된 간선을 제거하는데 정점6은 정점4가 있기 때문에

 

진입차수가 0이 아닌 1로 갱신된다. 이후에 정점3을 큐에서 꺼내 간선을 제거해주고 정점4를 큐에 담고 ...

 

위와 같은 방식을 반복적으로 수행해주면 결과적으로 진입차수는 모두 0이 되고 큐에서 원소를 꺼낸 순서는

 

1 - 2 - 5 - 3 - 4 - 6 - 7 이 된다. 이것이 위 그래프에서 위상 정렬을 수행한 결과이다.

 

[예제]

#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);
	} 
	for(int i=1; i<=n; i++) {
		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];
			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();
}

 

해당 소스코드는 C++로 작성한 코드이다.

 

우선 메인코드에서 정점의 개수와 각 정점을 연결한 그래프 형태를 정의한다. 각 정점을 연결해준 뒤 연결된 정점의

 

진입 차수를 1 증가시켜준다.

 

위상 정렬 알고리즘 수행에 해당하는 topologySort() 함수에서는 큐를 사용하도록 정의해준다. 그리고

 

진입 차수가 0인 노드를 push()해줌으로써 삽입한다.  두번째 반복문에서 정점의 개수만큼 반복문을 실행해주도록 하고

 

만약 n개를 방문하기 전에 큐가 빈다면 사이클이 발생한 것이기 때문에 출력문과 함께 실행을 중지한다.

 

큐가 비지 않는다면 큐에 가장 먼저 들어온 원소를 꺼낸 뒤 result[i] 에 담는다.

 

그 후, 반복문을 통해 새롭게 진입차수가 0이 된 정점을 큐에 삽입한다.

 

위와 같은 과정을 정점의 개수만큼 반복적으로 수행한다.

 

[결과]

위상 정렬(Topology Sort) 결과

 

---

출처

https://blog.naver.com/ndb796/221236874984

25. 위상 정렬(Topology Sort)