위상정렬
From Wikipedia, the free encyclopedia
위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다.
이 문서의 내용은 출처가 분명하지 않습니다. (2012년 3월) |
일반적인 위상 정렬의 적용은 주로 업무의 일정을 일어나야 할 순서에 따라 배치하기 위하는 것으로, 이 알고리즘은 프로젝트 관리 기법을 평가 및 분석하기 위한 기법(PERT)에 적용하기 위한 목적을 위해 1960년대 초반부터 연구되었다 (Jarnagin 1960). 이 때, 해당 업무는 꼭짓점으로 표현되었고, 각 꼭짓점을 연결하는 변은 해당 업무 간의 선후 관계를 표현하였다. 가령, 옷을 다리기 위한 업무는 반드시 옷을 세탁기에 돌리는 업무 뒤에 배치되어야 한다. 이와 같이, 위상정렬은 각 업무를 수행하기 위한 순서를 제공하였다.
Topological sorting(위상 정렬)은 컴퓨터 과학에서, 방향 그래프의 위상 정렬 또는 위상 배치는 정점의 선형 순서이다. 꼭짓점 u에서 꼭짓점 v로의 모든 방향 꼭짓점 uv는 v의 순서 전에 u가 오는 것이다. 예를 들어, 그래프의 꼭짓점은 아마 수행하는 일은 대표한다. 그리고 꼭짓점은 어떤 일이 다른 것보다 먼저 수행되어야 하는 허가되지 않은 것을 대표한다. 이러한 것에서, 위상 배열은 일의 유용한 순서에 불과하다. 정확히 위상 정렬은 모든 종속성을 방문한 후에만 각 노드 v를 방문하는 그래프 순환이다. 위상 배열은 가능하다. 정말 만약에 그래프 방향이 없는 순환이라면, 아마 그것은 방향 순환 그래프(DAG)일 것이다. 어떤 DAG는 최소 하나의 위상 배열을 가지고 있다. 그리고 알고리즘은 어떤 DAG 속 선형 시간의 위상 배열이 구성한다고 알려져 있다. 위상 정렬은 feedback arc set 와 같은 랭킹 문제를 해결하는데 많이 사용된다. 위상 정렬은 심지어 DAG의 요소가 연결되지 않을지라도 가능하다.