위상 정렬(Topology Sort)

위상 정렬(Topology Sort)이란?

 

자료구조에 있어서 수를 정렬하는 여러가지 알고리즘이 존재한다. 하지만 위상 정렬은 방향 그래프(Directed Graph)를 정렬하는 알고리즘이다. 쉽게 말해서 순서대로 작업을 수행할 수 있게 그 순서를 결정해주는 알고리즘이다.

 

 

스타크래프트라는 게임을 예로 들어보자.

 

탱크라는 유닛을 뽑고 싶다고 한다면

 

커맨더센터 짓기 - SCV 뽑기 - 서플라이 디팟 짓기 - 배럭 짓기 - 가스통 짓기 - 팩토리 짓기 - 탱크 뽑기

 

 

다음과 같이 탱크를 뽑기 위해서 그 전 작업을 만족해야 다음 작업을 진행할 수 있기때문에 작업의 순서를 정렬해주는 알고리즘이 필요하게 된 것이다. 그런데 여기서 가스통을 짓고 배럭을 지어도 논리적으로 문제가 없다. 팩토리를 짓기 위해 두 가지 작업이 선행되어야 한다는 논리는 같기 때문이다. 때문에 위상정렬은 여러 개의 답이 존재할 수 있다는 특징이 있다.

 

 

단 위상정렬을 하기 위해선 조건이 하나 필요하다. 그것은 DAG 그래프여야 한다는 것이다.

DAG(Directed Acyclic Graph)란 방향성은 있고, 사이클은 없는 그래프를 의미한다.

 

 

이제 실제 예를들어 그래프를 살펴보자. 위상정렬을 수행하게 되면 두 가지 해결책이 나온다.

1. 위상 정렬의 가능 여부    2. 그래프의 위상정렬 결과 

위상 정렬 알고리즘은 큐를 이용한 방식으로 풀어낼 수 있다. 

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

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

3. 간선을 제거한 후 다시 진입차수가 0인 정점을 큐에 삽입한다.

4. 2~3번을 반복하며 모든 원소를 방문하기 전에 큐가 비어있다면 사이클이 존재한 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상정렬 결과가 된다.

 

진입차수가 0인 노드 1을 큐에 삽입했다.

 

1과 연결된 간선을 모두 제거한다. 

다시 진입차수가 0인 2, 5 정점을 큐에 삽입한다.

2와 연결된 간선을 제거한다.

진입차수가 0인 3번 정점을 큐에 삽입한다.

5와 연결된 간선을 제거한다.

3과 연결된 간선을 제거한다.

과정에서 큐가 비어있지 않았고 모든 원소를 방문했기 때문에

1 -> 2 -> 5 -> 3 -> 4 -> 6 -> 7이 위상 정렬의 한가지 방법이 된다.

 

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63

#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;     // queue 생성     for(int i = 1; i <= n; i++) {         if(inDgree[i] == 0) q.push(i);     } // 노드 중 진입차수가 0인 것을 찾아 큐에 삽입       // 정확히 n개의 노드 모두를 방문한다.     for(int i = 1; i <= n; i++) {         // n개의 노드를 모두 방문하기 전 큐가 비었다면 사이클이 발생한 것이다.         // 따라서 if문을 통해 사이클 여부 확인         if(q.empty()) {             printf("사이클이 발생했습니다.");             return;         }         int x = q.front();         q.pop();         result[i] = x;         // 큐에 있는 노드를 꺼내 result 배열에 삽입         for(int i = i; 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();         }   Colored by Color Scripter

cs