[Algorithm] 위상 정렬(Topology Sort)

위상 정렬이란?

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

순차적으로 어떤 그래프가 형성되어있을 때, 그 그래프를 하나의 경로로 나타내는 것이다.

하나의 경로만 존재하는 것이 아니라, 여러 나열 방법이 있을 수 있기 때문에 답은 다양하게 나올 수 있는 알고리즘이다.

DAG(Directed Acyclic Graph: 사이클이 존재하지 않는 방향 그래프)에만 적용할 수 있다. 왜냐하면 시작점을 찾을 수 없기 때문이다.

위상정렬은 두 가지를 알려 준다.
1. 그래프의 위상 정렬 가능 여부

2. 만약 위상 정렬이 가능하다면, 그 결과

2가지 방법의 알고리즘이 있다.

1. 스택을 이용하는 방법

2. 큐를 이용하는 방법
   (큐가 일반적으로 많이 사용된다.)

큐를 이용한 위상정렬 원리

1. 진입 차수(특정한 노드가 있을 때, 그 노드로 들어오는 다른 노드의 수. 즉, 조건을 의미)가 0인 노드를 큐에 삽입(시작점을 뜻함)

2. 큐에서 원소를 꺼내서 연결된 간선 모두 제거

3. 진입 차수가 0이 된 다른 정점들을 큐에 다시 넣음

4. 큐가 빌 때까지 2번과 3번을 반복
   만약 모든 원소 방문 전에 큐가 빈다면, 사이클 존재

-> 큐에서 꺼낸 순서가 위상정렬의 결과

구현

시간 복잡도: O(V+E) 정점의 갯수 + 간선의 갯수

#include <iostream>
#include <vector>
#include <queue>

#define MAX 10 // 10개 만큼의 노드

using namespace std;

int n; 
int inDegree[MAX]; // 진입 차수 의미

vector<int> a[MAX]; // 각 정점에 연결되어 있는 모든 노드 정보

void topologySort() {
    int result[MAX]; // 위상정렬을 수행한 결과값 담는 배열
    queue<int> q;

    // 진입 차수가 0인 node 큐에 삽입
    for(int i=1;i<=n;i++) {
        if(inDegree[i] == 0) {
               q.push(i); 
        }
    }

    // 위상 정렬이 완전히 수행되려면 정확히 N개의 노드 방문해야함 
    for(int i=1;i<=n;i++) {
        // n개의 노드를 방문하기 전에 큐가 비면 사이클 발생 
        if(q.empty()) {
            printf("사이클이 발생했습니다.\n");
            return ;
        }
        // 큐의 가장 앞의 원소를 빼서 result 배열에 넣어줌 
        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); // 1번 노드 -> 2번 노드
    inDegree[2]++; // 2번 노드의 진입차수 1 증가

    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();
    return 0;
}

reference: https://www.youtube.com/watch?v=qzfeVeajuyc&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=27