위상정렬

날짜=2012-3-17 **위상 정렬**(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 그래프 구조 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다. 일반적인 위상 정렬의 적용은 주로 업무의 일정을 일어나야 할 순서에 따라 배치하기 위하는 것으로, 이 알고리즘은 프로젝트 관리 기법을 평가 및 분석하기 위한 기법(PERT)에 적용하기 위한 목적을 위해 1960년대 초반부터 연구되었다 (Jarnagin 1960). 이 때, 해당 업무는 꼭짓점으로 표현되었고, 각 꼭짓점을 연결하는 변은 해당 업무 간의 선후 관계를 표현하였다. 가령, 옷을 다리기 위한 업무는 반드시 옷을 세탁기에 돌리는 업무 뒤에 배치되어야 한다. 이와 같이, 위상정렬은 각 업무를 수행하기 위한 순서를 제공하였다. Topological sorting(위상 정렬)은 컴퓨터 과학에서, 방향 그래프의 위상 정렬 또는 위상 배치는 정점의 선형 순서이다. 꼭짓점 u에서 꼭짓점 v로의 모든 방향 꼭짓점 uv는 v의 순서 전에 u가 오는 것이다. 예를 들어, 그래프의 꼭짓점은 아마 수행하는 일은 대표한다. 그리고 꼭짓점은 어떤 일이 다른 것보다 먼저 수행되어야 하는 허가되지 않은 것을 대표한다. 이러한 것에서, 위상 배열은 일의 유용한 순서에 불과하다. 정확히 위상 정렬은 모든 종속성을 방문한 후에만 각 노드 v를 방문하는 그래프 순환이다. 위상 배열은 가능하다. 정말 만약에 그래프 방향이 없는 순환이라면, 아마 그것은 방향 순환 그래프(DAG)일 것이다. 어떤 DAG는 최소 하나의 위상 배열을 가지고 있다. 그리고 알고리즘은 어떤 DAG 속 선형 시간의 위상 배열이 구성한다고 알려져 있다. 위상 정렬은 feedback arc set 와 같은 랭킹 문제를 해결하는데 많이 사용된다. 위상 정렬은 심지어 DAG의 요소가 연결되지 않을지라도 가능하다.
# 위상정렬의 수행과정
# 자기 자신을 가리키는 변이 없는 꼭짓점을 찾음. # 찾은 꼭짓점을 출력하고 출력한 꼭짓점과 그 꼭짓점에서 출발하는 변을 삭제 # 아직 그래프에 꼭짓점이 남아있으면 단계 1로 돌아가고, 아니면 알고리즘을 종료시킨다.
# 예시
위상 정렬의 기본 적용은 그들의 종속성을 기반으로하여 일 또는 직업의 연속된 일정에 있다. 이 일은 꼭짓점에 대해 대표된다. 그리고 x로부터 y로의 모서리가 있다. 만약 일 x가 일 y가 시작하기 전에 끝났다.그런 다음, 위상 정렬은 일을 수행한 순서를 준다. 가까운 관계된 위상 정렬 알고리즘의 적용은 1960년에 프로젝트 관리에서 스케줄링을 위한 PERT 기술의 맥락에서 처음으로 학습한다. 이러한 적용은, 그래프의 꼭짓점을 대표한다. 프로젝트의 중요한 단계와 모서리는 하나의 중요한 단계와 다른 것 사이 수행된 일을 대표한다. 위상 정렬은 프로젝트의 치명적인 방법을 찾기 위해 선형 시간 알고리즘으로부터 왔다. 중요한 일의 연속은 종합적인 일정의 길이를 통제한다. 컴퓨터 과학에서, 이러한 유형의 적용은 일정을 구성하면서 발생한다. 세포 진화 공식의 순서는 스프레드 시트나 종합 논리를 다시 공식을 계산한 가치가 있을 때, 생성 파일에서 일을 완벽히 수행하는 것을 결정한다. 데이터 직렬화, 그리고 되풀이 상징은 링커들에 달려있다. 또한 데이터 베이스에서 외래 키가 있는 테이블을 가져오는 순서를 결정하는데 사용된다. {| |left | 왼쪽의 그래프는 많은 유용한 위상 정렬을 보여준다. * 5, 7, 3, 11, 8, 2, 9, 10 ( 맨 위에서 왼쪽에서 오른쪽으로 아래까지 ) * 3, 5, 7, 8, 11, 2, 9, 10 ( 제일 작은 수부터 이용 가능한 첫 꼭짓점까지 ) * 5, 7, 3, 8, 11, 10, 9, 2 ( 왼쪽 맨 위를 처음으로 ) * 7, 5, 11, 3, 10, 8, 9, 2 ( 가장 큰 수부터 이용 가능한 첫 꼭짓점까지 ) * 7, 5, 11, 2, 3, 8, 9, 10 ( 맨 위부터 왼쪽에서 오른쪽으로 시도하여 아래까지 ) * 3, 7, 8, 5, 11, 10, 2, 9 ( 제멋대로 ) |}
# 알고리즘
위상 정렬의 일반적인 알고리즘은 꼭짓점의 양수 노드의 선형 실행 시간을 가진다. O(\left|{V}\right| + \left|{E}\right|).
## Kahn의 알고리즘
Kuhn의 알고리즘과 헷갈리지 않도록 주의! 위상 정렬 알고리즘 중 하나이다. Kahn에 의해 1962년에 처음으로 언급되었다. 궁극적인 위상 정렬로써 같은 순서 속에 일은 꼭짓점에 의해 선택된다. 처음으로, “시작 노드”를 찾는다. 꼭짓점과 연결되지 않고, S집합에 연결되어 있는; 적어도 하나의 노드는 비어있지 않은 순환 그래프 안에 존재한다. *L* ← Empty list that will contain the sorted elements *S* ← Set of all nodes with no incoming edge **while** *S* **is not** empty **do** remove a node *n* from *S* add *n* to *L* **for each** node *m* with an edge *e* from *n* to *m* **do** remove edge *e* from the graph **if** *m* has no other incoming edges **then** insert *m* into *S* **if** *graph* has edges **then** **return** error *(graph has at least one cycle)* **else** **return** *L* *(a topologically sorted order)* 만약 그래프가 DAG라면, 해결책은 L 리스트(해결책은 특별한 것이 필요 없다.) 안에서 억제하는 것이다. 마찬가지로, 그래프는 적어도 하나의 순환을 가지고 있어야 한다. 그러므로 위상 정렬은 불가능하다. 결과적으로 정렬의 특별하지 않은 것을 반영하여, 구조 S는 Set 또는 queue 또는 stack으로 간단화 할 수 있다. 순서에 의해, 노드 n들은 집합 S로부터 제거된다. 그리고 다른 해결책을 생성한다. kahn의 알고리즘의 변형은 연병렬 스케줄링 및 계층 그래프 그리기를 위한 Coffman-Graham 알고리즘의 핵심 구성 요소를 사전식으로 연결을 끊는다.
## 깊이 우선 탐색
위상 정렬의 대체 가능한 대안 알고리즘은 깊이 우선 탐색을 기반으로 한다. 알고리즘의 임의적인 순서 속 그래프의 각 노드를 통한 루트는 그것이 이미 시작 이후로 거쳐간 노드의 위상 정렬 또는 꼭짓점을 가지지 않은 다른 노드를 건들 때 착수한 깊이 우선 탐색이 제거한다. *L* ← Empty list that will contain the sorted nodes **while** exists nodes without a permanent mark **do** select an unmarked node *n* visit(*n*) **function** visit(node *n*) **if** *n* has a permanent mark **then** **return** **if** *n* has a temporary mark **then** **stop** *(not a DAG)* mark *n* with a temporary mark **for each** node *m* with an edge from *n* to *m* **do** visit(*m*) remove temporary mark from *n* mark *n* with a permanent mark add *n* to head of *L* 각 노드 n은 출력 리스트 L에서 모든 다른 노드를 고려한 후에 n에 의존한다. 특히 알고리즘이 노드 n을 추가할 때, 우리는 모든 노드가 n에 의존한다는 것을 보장하는 것은 이미 출력 리스트 L에 있다는 것이다. : 그들은 되풀이 되는 방문 호출에 의해 n에 방문하기 전에 끝나거나, n이 호출되기 전에 끝나는 것 둘 다 L에 추가한다. 각 꼭짓점과 노드가 하나를 방문한 이래로, 알고리즘은 선형 시간에서 실행한다. 그리고 깊이 우선 탐색의 기초 알고리즘은 Cormen et al에 의해 2001년에 만들어진다. 그것은 1976년 Tarjan 인쇄에서 처음 만들어져 온 것처럼 보인다.
## Parallel 알고리즘
Parallel의 랜덤 접속 기계에 의하면, 위상 배치는 *O*(log2 *n*) 시간 안에 다수의 프로세서를 사용해 구성할 수 있다. 문제 속 복잡한 클래스 *NC2*'.을 넣는다. 이를 수행하는 한 가지 방법은 주어진 그래프, 논리적 시간의 인접 행렬을 반복적으로 제곱하는 것이다. 결과 행렬은 가장 긴 길이가 그래프에서 줄어들게 만든다. 꼭짓점을 정렬하는 것은 그들의 가장 긴 방법의 길이에 의해 위상 배치를 생성한다.
# 최단 거리 찾기에서 적용
위상 배치는 역시 길이의 DAG를 통해서 최단 거리를 빠르게 계산하는데 사용된다. V를 토폴로지 순서로 이러한 그래프의 정점 목록이라고 하자. 그런 다음 알고리즘을 따라 최단 거리를 계산한다.

blue * d를 V와 같은 길이의 배열이라고 하자. 이것은 s에서 최단 경로 거리를 유지한다. 1=*d*[*s*] = 0, 1=*d*[*u*] = ∞. * p를 V와 동일한 길이의 배열로, 모든 요소는 nil로 초기화한다. 각*p*[*u*]는 s에서 u까지의 최단 경로에서 u의 선행자를 보유한다. * s에서 시작하여 V에서 순서대로 정점 u를 반복한다. : ** u 바로 뒤에 오는 각 꼭짓점 v에 대해 (즉, u에서 v까지의 간선이 존재한다.): *** w를 u에서 v까지의 간선의 가중치라고 하자. *** 가장자리를 풀다. : if *d*[*v*] > *d*[*u*] + *w*, set **** *d*[*v*] ← *d*[*u*] + *w*, **** *p*[*v*] ← *u*. frame-footer

그래프의 n 꼭짓점과 m 꼭짓점에서, 이 알고리즘은 O(*n* + *m*). 즉, 선형 시간에 실행이 된다.
# 독특한 점
만약 위상 정렬이 모든 연속된 꼭짓점을 모서리가 연결된 정렬 배치에서 소유한다면, DAG 속 Hamiltonian path로부터 모서리이다. 만약 Hamiltonian path가 존재한다면, 위상 정렬 배치는 독특한 것이다; 다른 모서리의 길 배치는 고려하지 않는다. 정반대로, 만약 위상 정렬이 Halmiltonian path로부터 온 것이 아니라면, DAG는 두 가지 또는 더 많은 종류의 위상 배치를 가질 것이다. 이러한 경우 이것은 항상 두 연속된 점이 각각 연결되지 않는 것이 가능하다. 그러므로, 그것은 선형 시간에서 독특한 배치가 존재하던 아니던, 그리고 Hamiltonian path가 존재하던 아니던, 보다 일반적인 방향 그래프에 대한 Hamiltonian path 문제의 NP경도에도 불구하고 테스트가 가능하다.( 즉, 순환 그래프이다. )