[Algorithm] Topological Sort

topological sort

**위상정렬(topological sort)**이란 일반적인 정렬과는 다르다. 위상정렬은 Graph에서 쓰이는 정렬 기법중 하나이다.

선행 조건은 그래프가 DAG(directed acycle graph)이여야 한다.

쉽게 설명하자면, 다음과 같다.

우리는 책상정리를 해야 공부를 할 수 있다.

또한 책상정리를 하려면 쓰레기봉투를 사야한다.

또 공부를 하려면 일단 잠을 자야한다.

등등 공부를 하려면 일단 많은 일을 해야한다. 이를 직관적 그래프로 그려보면 아래와 같다.

그럼 공부를 시작하기 전에 무엇부터 해야하지?

공부하기 전에 반드시 을 자야한다. 또한 반드시 책상정리맥주한잔을 해야한다.

하지만 을 먼저 자던 책상정리를 먼저하던 그건 상관이 없다.


위상 정렬은 이렇게 DAG를 할일순? 으로 정렬하는 기법이다.

즉!! 눈치를 챗겠지만, 위상정렬은 그 해가 여러개일수 있다.

1. 잠자기->쓰레기봉투구입->책상정리->친구불러내기->맥주한잔->공부
2. 쓰레기봉투구입->잠자기->친구불러내기->맥주한잔->책상정리->공부

위에서 보듯 둘중에 어떤 방법으로 일을 수행해도, 문제가 없다.

정렬 기법은 간단하다.

먼저 DFS를 통해 각 정점을 순회한다. 그 후, 순회 순서를 역으로 출력하면된다.

만일 STL의 경우 DFS함수의 끝 부분에 list::push_front 등을 통해 각 정점을 삽입하면,

그 자체가 위상정렬을 한 결과가 된다.

int N, M;
vector<vector<int> > G;	//인접 리스트
vector<bool> visit;		//방문 확인 
list<int> tlist;		//위상정렬 결과 리스트
void DFS(int v) {
    visit[v] = true;
    for (int i = 0; i < G[v].size(); i++){
        if (!visit[G[v][i]]){
            DFS(G[v][i]);
        }
    }
    tlist.push_front(v);	//방문할곳이 없으면 앞으로 추가
}
void TopoLogicalSort() {
    tlist.clear();
    visit.assign(N, false);
    for (int i = 0; i < G.size(); i++){
        if (!visit[i]){
            DFS(i);
        }
    }
}
"위상정렬은 그래프를 바꾸지 않는다."

아래는 위상정렬을 이용한 간단한 문제이다.

https://www.acmicpc.net/problem/2252

Copyright (C) 2016 (KimBom) all rights reserved.