위상 정렬(topological sort)

위상 정렬(topological sort)

 

출처: 알고리즘 문제 해결 전략
관련문제: AOJ DICTIONARY

 

위상 정렬이란 우선순위가 있는 그래프의 정점을 배열하는 것을 말한다.

(ex) 덧셈을 배워야 곱셈을 배울 수 있다.)

 

흔히 DFS를 이용하여 위상 정렬 배열을 구하는데 아래 그래프와 소스코드를 잘 보면

order 백터에는 4, 3, 6, 7, 5, 2, 9, 8, 1이 순서대로 값이 저장된다.

결과는 DFS가 늦게 종료한 정점일수록 정렬결과의 뒤에 온다.

1을 방문해야 8을 갈수 있고 8을 방문해야 9를 갈수잇고-----------------3을 방문해야 4를 갈 수 있다.

<소스 코드>

[-] Collapse

#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

vector<vector<int> > adj;

void makeGraph(const vector<string>& words){
    adj = vector<vector<int> >(26, vector<int>(26, 0));
    for (int j = 1; j < words.size(); ++j) {
        int i = j - 1, len = min(words[i].size(), words[j].size());
        for (int k = 0; k < len; ++k){
            if (words[i][k] != words[j][k]) {
                int a = words[i][k] - 'a';
                int b = words[j][k] - 'a';
                adj[a][b] = 1;
                break;
            }
        }
    }
}

vector<int> seen, order;
void dfs(int here){
    seen[here] = 1;
    for (int there = 0; there < adj.size(); there++){
        if (adj[here][there] && !seen[there])
            dfs(there);
    }
    order.push_back(here);
}

vector<int> topologicalSort() {
    int n = adj.size();
    seen = vector<int>(n, 0);
    order.clear();
    for (int i = 0; i < n; i++) if (!seen[i]) dfs(i);
    reverse(order.begin(), order.end());
    for (int i = 0; i < n; i++){
        for (int j = i + 1; j < n; j++)
        //DAG가 아니라면 빈백터 리턴
        if (adj[order[j]][order[i]])
            return vector<int>();
    }
    return order;
}