[Algorithm] Topology Sort (위상 정렬)

 

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

 

위상정렬은 여러 개의 답이 존재할 수도 있고 사이클이 발생하는 경우 수행이 불가능하다는 특징이 있다.

 

 

 

위상 정렬 수행으로는 스택과 큐를 사용하는 데 큐로 더 고급적인 수행이 가능하다고 인강에선 큐를 이용하여 소스를 작성하였다.

 

순서로는

 

1. 진입차수가 0인 정점을 큐에 삽입
2. 큐에서 원소를 꺼내어 연결된 모든 간선 제거
3. 간선 제거 이후 진입차수가 0이 되는 정점을 큐에 삽입
4. 큐가 빌 때까지 2,3번 과정 반복
   - 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재한다는 것
5. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과임

 

위 그림을 표로 나타내면

 

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

 

 

** C++

 

#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);
	} 
	
	// 정렬이 완전히 수행되기 위해 정확히 n개의 노드를 방문
	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];
			// 새롭게 진입차수가 0인 정점을 큐에 삽입
			if (--inDegree[y] == 0) {
				q.push(y);
			} 
		}
	}
	
	for (int i = 1; i <= n; i++) {
		printf("%d ", result[i]);
	} 
}

int main(void) {
	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();
}

 

 

** Python

 

from collections import deque

number = 7
indegree = [0] * (number + 1);
graph = [[] for i in range(number + 1)]

def topologySort():
    # 알고리즘 수행 결과
    result = []
    # 큐
    q = deque()
    
    # 진입 차수가 0인 노드를 큐에 삽입
    for i in range(1, number + 1):
        if indegree[i] == 0:
            q.append(i)
            
    # 큐가 빌 때까지 반복
    while q:
        # 큐에서 원소 꺼내기
        now = q.popleft()
        result.append(now)
        
        # 해당 원소와 연결된 노드들의 진입차수에서 1 빼기
        for i in graph[now]:
            indegree[i] -= 1
            
            # 새롭게 진입차수가 0이 되는 노드를 큐에 삽입
            if indegree[i] == 0:
                q.append(i)
                
    for i in result:
        # 결과 출력
        print(i)

if __name__ == "__main__":
    number = 7
    graph[1].append(2)
    indegree[2] += 1
    graph[1].append(5)
    indegree[5] += 1
    graph[2].append(3)
    indegree[3] += 1
    graph[3].append(4)
    indegree[4] += 1
    graph[4].append(6)
    indegree[6] += 1
    graph[5].append(6)
    indegree[6] += 1
    graph[6].append(7)
    indegree[7] += 1
    topologySort();

 

 

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

모든 노드를 확인하고 해당 노드에서 출발하는 간선을 차례대로 제거하면서 노드와 간선을 모두 확인하기 때문이다.