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.

springkim

Add Comment

Graph

2016년 4월 30일 토요일

Bipartite Graph Bipartite Graph 1. 이분그래프 정의 이분 그래프란 모든Edge(간선)이 U(위쪽의 Vertex)와 V(아래의 Vertex)사이를 잇는 형태의 그래프 이다
Bellman-Ford Algorithm Bellman Ford Algoritm 그래프에서 최단경로 탐색 문제에 대한 3가지 알고리즘이있다. Bellman-Ford Algoritm (벨만-포드 알고리즘) Di
Dijkstra Algorithm Dijkstra Algorithm 앞서 소개한 벨만포드보다 향상된 기법(?)의 다익스트라 알고리즘에대해 알아보자. 1. 다익스트라 알고리즘 소개 먼저 다익스트라 알고
Graph Basic Theory Graph Basic Theory 1.그래프의 정의 그래프란 vertex와 edge로 구성되어 있다. vertex(정점)은 node(노드)와 비슷한 의미이며 보통의

The revolution

Problem

Solving

topological sort

topological sort

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

Related Posts