위상정렬

위상정렬은 정렬 알고리즘의 종류이다.

 

위상정렬이란 '방향그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열' 하는 것이다.

 

쉽게 비유를 하자면 '대학교 커리큘럼'을 예로들수있다. 

 

예를들어 모 대학교의 컴공과는 인공지능과목을 자료구조를 선수강한 뒤에 신청할수있도록 하였다. 

 

이처럼 그래프상에서 선후관계가있다면, 위상 정렬을 수행하여 모든 선후 관계를 지키는 순서를 계산할수있다.

 

위상정렬의 알고리즘 순서는 다음과 같다.

 

1. 진입차수가 0인 노드를 큐에 넣는다.

2. 큐가 빌때 까지 다음의 과정을 반복한다.

    1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다.

    2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다.

 

 

여기서 진입 차수란, 특정노드로 들어오는 간선의 개수와 같다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int V ,E;
int indegree[100001];
vector<int> graph[100001];

void topologySort(){
    vector<int> result; 
    queue<int> q;

    for(int i = 1 ;i <= V ; i++){
        if(indegree[i] == 0) q.push(i);
    }

    while (!q.empty()){
        int now = q.front();
        q.pop();
        result.push_back(now);

        for(int i = 0 ; i < graph[now].size(); i++){
            int pri = graph[now][i]; // 현재 노드에 진입하는 노드들
            indegree[pri] --;
            if(indegree[pri] == 0 ){
                q.push(pri);
            }
        }
    }
    for (int i = 0; i < result.size(); i++) { //정렬결과 출력
        cout << result[i] << ' ';
    }

}
int main(){
    cin >> V >> E;
    for(int i = 0; i< E;i++){
        int v1 ,v2;
        cin >> v1 >> v2;
        graph[v1].push_back(v2);
        indegree[v2]+=1;
    }
    topologySort();
    return 0;
}

 

위상정렬의 복잡도는 O (V + E) 이다. 차례대로 모든 노드를 확인 하면서 해당노드에서 출발하는 간선을 제거해야한다.