위상정렬(Topological Sort)

여기참조

 

유향그래프가 있을 때, 오더링 하는 방법론에 대한게 위상정렬이고, 

DFS를 이용한 방법(DFS Spanning Tree)과

Queue를 이용한 방법(indgree)이 있다. 나한테는 이방식이 편했다.

위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(DAG)여야 한다.

 

사이클이 있는 경우는 오더링이 불가 하고, DFS와 Queue모두 이를 중간 과정을 통해 디텍트 할 수 있다.

 

위키피디아의 다음 설명을 읽어보자

위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 

그렇다면 위상정렬과 DAG과의 관계는 무엇인가.. 위상정렬이 가능하려면 (사이클이 없는) DAG이어야 한다고 말할 수 있다.

 

위상정렬에 대한 풀어보면 좋은 문제는 다음과 같다.

 

백준 ACM Craft : 바닐라 한데, 제약조건이 좀 빡빡하다(100,000이라 adjacent matrix 사용 불가)

 

 

BFS방식

여기 예제를 통한 설명 좋다.

일반 BFS와의 차이점은 사이클 처리를 위해서 while(q.empty()==false) 이걸로 루프돌리는게 아니라,

for(int i=0;i<N;i++) 이걸로 루프돌리는게 특이하고, 인접리스트와 별도로 in-edge카운팅해줘서 0이되는것만 enqueue하면 된다.

아래는 내가 구현하고 이 문제로 검증한 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REP1(i,n) for(int i=1;i<=(int)(n);i++)
using vi = vector<int>;
using vvi = vector<vi>;
#define OUT(x) {cout << (x) << '\n'; }
#define IN(n) int n;cin>>n
 
int32_t main()
{
    FastIO; IN(N); IN(M);
    vi in(N + 1); // in-edge를 관리해주는게 핵심
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        IN(u); IN(v); adj_list[u].push_back(v); in[v]++;
    }
    queue<int> q;
    function<void(int n)> enqueue = [&](int n) {
        if ((in[n]--) > 0) return;
        q.push(n);
    };
    vi ans;
    REP1(i, N) enqueue(i);
    while (N--) {  // 정확히 n번 dequeue로 끝난다.
        if (!q.size()) { break; }//cycle!
        int n = q.front(); q.pop();
        ans.push_back(n);
        for (auto adj : adj_list[n]) {
            enqueue(adj);
        }
    }
    for (auto a : ans) cout << a << ' ';
    return 0;
}

 

 

DFS방식

BFS방식이 좀 더 직관적이긴 하지만, DFS방식은 DP연계가 쉽다는 점에서 알아둘 필요가 있다.

DFS방식은 말하자면 다음과 같다.

DFS로 방문할 수 있는 모든 노드를 재귀적으로 방문한뒤..
방문할 수 있는 next가 없으면
topological_sort 와 같은 큐에 데이터를 집어넣고, 이를 역순으로 표시

여기를 보면 알기 쉽게 설명돼있다. 위의 BFS버전과 같은 문제에 대한 답안이기도 하다.

DFS의 경우는 in-edge관리를 안해줘도 돼서 어떻게 보면 훨씬 더 다루기 쉽다. (사이클 처리는 대신 약간 복잡)

#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
using vvi = vector<vi>;
struct result { bool cycle; vi sorted; };
result topological_sort(int max_v, int start_v, vvi& adj_list, bool base1=false) {
    if (base1) max_v++;
    // cycle 검출을 위해 finish배열 하나더 기용해준다.
    // visit되고 finish되기전에 다시 방문되면 사이클로 보는것
    vi visit(max_v), finish(max_v);
    result r = { false, vi() };
    deque<int> sorted; bool cycle = false;
    function<void(int)> dfs = [&](int v) {
        visit[v] = 1;
        for (auto adj : adj_list[v]) {
            if (visit[adj] == 0) dfs(adj);
            else if (finish[adj] == 0) {
                cycle = 1;// visit은 1인데, finish 는 0으로 들어왔다? cycle!
            }
        }
        finish[v] = 1;
        sorted.push_front(v);
    };
    if (start_v == -1) {
        for (int i = (int)base1; i < max_v; i++) 
            if (visit[i] == 0) dfs(i);
    }
    else dfs(start_v);
    return { cycle, vi(sorted.begin(), sorted.end()) };
}
 
int32_t main()
{
    int N, M; cin >> N >> M;
    //vi in(N + 1);  // DFS버전에서는 in-edge관리를 안해도 된다.
    vvi adj_list(N + 1);
    for (int i = 0; i < M; i++) {
        int u, v; cin >> u >> v; adj_list[u].push_back(v);
    }
 
    // 일단 아이디어는 DFS돌려서 말단까지 가고,
    // 거기서 부터 stack에 넣어주면 위상정렬 정순위가 된다는것.
    result r = topological_sort(N, -1, adj_list, true);
    for (auto a : r.sorted) cout << a << ' ';
    return 0;
}

그런데, visit, finish 처리를 위처럼 하면 경로 카운팅 문제에서는 문제가 생긴다.

예를 들어 1번 정점에서 2번 정점으로의 경로가 하나가 아니라 여러개인경우,

visit만 1인상태에서 finish전에 여러경로를 다 세주어야 하는데,

if (visit[adj] == 0) dfs(adj) 이부분 때문에 하나의 경로만 카운팅 되는 것