[Algorithm] 위상 정렬(Topology Sort)

위상 정렬(Topology Sort)에 대해서 공부하고 정리한 내용입니다.

잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다!

 

 

 

위상 정렬(Topology Sort)이란?

 

방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다.

쉽게 이야기 하자면 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용합니다.

 

위상 정렬의 실생활 예시는 대학교의 선수 과목 구조를 예로 들 수 있습니다.

 

웹 프로그래밍 과목을 듣기 위해 컴퓨터 기초, 컴퓨터 프로그래밍 그리고 UNIX 시스템 과목을 먼저 들어야 합니다.

이렇게 순서가 있는 작업이 있을 때 작업을 정확하게 정렬해주는 위상 정렬 알고리즘을 사용합니다.

 

위 예시의 순서를 찾는다면 아래와 같습니다.

위상 정렬 : 컴퓨터 기초 ➜ UNIX 시스템 ➜ 컴퓨터 프로그래밍 ➜ C++ 프로그래밍 ➜ 시스템 프로그래밍 ➜ 웹 프로그래밍 ➜ 운영체제

 

위의 순서 외에도 다른 순서도 존재합니다.

위상 정렬 : 컴퓨터 기초 ➜ UNIX 시스템 ➜ 컴퓨터 프로그래밍 ➜ C++ 프로그래밍 ➜ 웹 프로그래밍 ➜  시스템 프로그래밍 ➜ 운영체제

그러므로 여러 개의 답이 존재 할 수 있습니다.

 

또한 위상 정렬은 사이클이 발생하지 않는 그래프(Directed Acyclic Graph)에서만 적용이 가능합니다.

사이클이 발생하는 경우 위상 정렬을 수행할 수 없습니다.

 

 

 

위상 정렬(Topology Sort) 알고리즘

 

위에서 예시로 들었던 그래프의 정점을 숫자로 표기하도록 하겠습니다.

 

 

위상 정렬 알고리즘은 스택을 사용하는 방법과 큐를 사용하는 방법이 있습니다.

큐를 사용하는 방법에 대해서 적어보려고 합니다.

 

❶ 진입 차수가 0인 정점을 큐에 삽입합니다.

여기서 진입 차수란?

한 정점에 들어오는 간선의 개수 입니다.

위 예시에서 3번 정점은 들어오는 간선의 개수가 1개이므로 진입 차수가 1입니다.

하지만 6번 정점은 들어오는 간선의 개수가 2개이므로 진입 차수가 2입니다.

 

❷ 큐에서 원소를 꺼내고 꺼낸 원소를 결과 배열에 추가합니다.

그리고 연결된 모든 간선을 제거합니다.

❸ 간선 제거 이후 진입 차수가 0이된 정점을 큐에 삽입합니다.

❹ 큐가 빌 때까지 2 ~ 3번 과정을 반복합니다.

❺ 마지막으로 결과 배열의 크기와 정점의 개수가 같다면 사이클이 존재하지 않는 것이고, 다르다면 사이클이 존재하는 것입니다.

 

 

위의 방법대로 위상 정렬 알고리즘을 설명해보자면

처음 각 정점과 진입 차수 정보를 기록해둡니다.

 

다음은 진입 차수가 0인 정점을 큐에 삽입합니다.

 

 

큐에 있는 1번 정점을 빼낸 후 1번과 연결된 간선을 제거합니다.

 

 

큐에서 2번 정점을 빼냅니다. 그리고 2번 정점과 연결된 간선을 제거합니다.

 

큐에서 3번 정점을 빼냅니다. 그리고 3번 정점과 연결된 간선들을 모두 제거합니다.

간선 제거 이후 진입 차수가 0이된 정점들을 큐에 삽입합니다.

 

큐에서 4번 정점을 빼냅니다.

 

큐에서 5번 정점을 빼냅니다. 5번 정점과 연결된 간선을 제거합니다.

간선 제거 이후에 진입 차수가 0이 된 정점을 큐에 삽입합니다.

 

큐에서 6번 정점을 빼냅니다.

 

마지막으로 큐에서 7번 정점을 빼냅니다.

 

결과적으로 순서는 큐에서 정점을 꺼내는 순서이고

1 ➔ 2 ➔ 3 ➔ 4 ➔ 5 ➔ 6 ➔ 7 이 정답이 됩니다.

 

 

 

위상 정렬(Topology Sort) 알고리즘 구현(C++)

 

위의 내용을 기반으로 위상 정렬 알고리즘을 구현하면 아래와 같습니다.

 

#include <bits/stdc++.h>
#define MAX 10
using namespace std;

vector<int> graph[MAX];
int N;
int degree[MAX];

queue<int> q;
vector<int> result;

void topologySort() {
    
    for(int i = 1; i <= N; ++i) {
        if(degree[i] == 0) q.push(i);
    }

    while(!q.empty()) {
        int cur = q.front();
        q.pop();
        result.push_back(cur); 
        for(int next : graph[cur]) {
            degree[next] -= 1;
            if(degree[next] == 0) q.push(next);
        }
    }

    if(result.size() != N) {
        cout << "cycle exist" << '\n';
        return;
    } else {
        for(int element : result) cout << element << ' ';
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    N = 7;
    graph[1].push_back(3);
    degree[3] += 1;
    graph[2].push_back(6);
    degree[6] += 1;
    graph[3].push_back(4);
    degree[4] += 1;
    graph[3].push_back(5);
    degree[5] += 1;
    graph[3].push_back(6);
    degree[6] += 1;
    graph[5].push_back(7);
    degree[7] += 1;

    topologySort();
    return 0;
}