위상정렬 (Topological Sort)

목표 : 위상정렬에 대해 이해하고 위상정렬을 코드를 구현할 수 있다.

위상정렬 (Topological Sort)

유향 그래프의 꼭짓점들을 변의 방향을 거스르지 않도록 나열하는 것.

위상정렬이 성립하기 위해선 Cycle이 존재해선 안된다.

선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상정렬을 사용함

1. DFS를 이용하여 위상정렬을 구현한다.

DFS를 실행하면서 DFS가 끝나는 순서대로 기록하면 그 역순이 위상정렬이 된다.

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

bool visited[1010];
bool finish[1010];
vector<vector<int>>vec;
stack<int> TopoloStack;
int TopologicalSortDfs(int here) {
    for(int there : vec[here]) {
        if(!visited[there]) {
            visited[there] = true;
            TopologicalSortDfs(there);
        } else if(finish[there]) {
            return -1;
        }
    }
    finish[here] = true;
    TopoloStack.push(here);
    return 1;
}

DFS가 끝난 다음 stack에 있는 값을 pop 하며 출력하면 위상정렬된 결과가 나온다.