[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.