위상정렬

💻 위상정렬(Topology sort)

순서가 정해져있는 작업의 순서 결정 알고리즘

위상정렬은 그래프의 프름을 보고 그 작업의 수행 순서를 결정하기 위해 사용하는 알고리즘이다.
하지만 해당 알고리즘에는 조건이 있다!
사이클이 발생하지 않는 방향그래프 에서만 사용이 가능하다!

해당 알고리즘을 사용하는 경우 2가지의 문제상황을 해결할 수 있다
1. 현재 그래프가 위상정렬이 가능한지! 👉 사이클이 발생하지 않는 방향그래프인지 확인
2. 위상정렬이 가능하다면 그 결과 즉, 작업의 순서는 어떠한지!

를 해결할 수 있다.

해당 알고리즘을 사용하는 방법은 스택과 큐가 존재한다.

📙 Queue를 사용하는 경우

1. 진입차수가 0인 정점을 큐에 삽입한다.
2. 큐에서 원소를 꺼내 연결된 모든 간선(현재 노드를 거쳐야 하는 모든 노드의 진입차수 감소)를 제거한다.
3. 간선 제거 이후(진입차수 감소 이후) 진입차수가 0인 정점을 큐에 삽입한다.
4. 위의 과정을 큐가 빌때까지 반복한다!
   • 모든 원소 방문 이전 큐가 빈다면 사이클이 존재하는 것이다!

📙 관련 문제

줄 세우기

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>

using namespace std;

vector<int> path[32001];
int indegree[32001];
int result[32001];
int n, m;

void sorting();

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m;

    for(int i=0; i<m; i++) {
        int a, b;
        cin>>a>>b;
        path[a].push_back(b);
        indegree[b]++;
    }

    sorting();
}

void sorting() {
    queue<int> q;

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

    for(int i=1; i<=n; i++) {
        if(q.empty()) return;

        int cur = q.front();
        q.pop();
        result[i] = cur;

        for(int i=0; i<path[cur].size(); i++) {
            int now = path[cur][i];
            if(--indegree[now] == 0) q.push(now);
        }
    }

    for(int i=1; i<=n; i++) {
        cout<<result[i]<<" ";
    }
    cout<<endl;
}