토폴로지 정렬

컴퓨터 과학에서 유향 그래프의 위상 정렬 또는 위상 순서는 정점 u에서 정점 v까지의 모든 유향 edge uv에 대해 u가 순서 v보다 앞에 오도록 하는 정점의 선형 순서입니다.예를 들어 그래프의 꼭지점은 수행할 태스크를 나타낼 수 있으며, 가장자리는 다른 태스크보다 먼저 수행해야 하는 제약조건을 나타낼 수 있습니다. 이 응용 프로그램에서 위상 순서는 태스크에 대한 유효한 시퀀스일 뿐입니다.정확히 말하면, 토폴로지 정렬은 각 노드 v가 모든 종속성을 방문한 후에만 방문하는 그래프 트래버설입니다.위상 순서는 그래프에 유도 사이클이 없는 경우, 즉 유도 비순환 그래프(DAG)인 경우에만 가능합니다.모든 DAG는 적어도 1개의 토폴로지 순서를 가지며 알고리즘은 임의의 DAG의 토폴로지 순서를 선형 시간으로 구성하는 것으로 알려져 있다.위상 정렬은 특히 피드백 호 집합과 같은 순위 문제에 많이 적용됩니다.DAG에서 구성 요소의 연결이 끊긴 경우에도 토폴로지 정렬이 가능합니다.

예

위상 정렬의 표준 적용은 종속성을 기반으로 작업 또는 태스크의 시퀀스를 스케줄링하는 데 있습니다.작업은 정점으로 표시되며, 작업 y를 시작하기 전에 작업 x를 완료해야 하는 경우(예를 들어 빨래를 세탁할 때 빨래를 건조기에 넣기 전에 세탁기를 완료해야 함)에는 x에서 y까지의 가장자리가 있습니다.그런 다음 토폴로지 정렬에 따라 작업을 수행할 순서가 지정됩니다.토폴로지 정렬 알고리즘의 밀접하게 관련된 적용은 프로젝트 ^[1]관리의 스케줄링을 위한 PERT 기법의 맥락에서 1960년대 초에 처음 연구되었다.이 응용 프로그램에서 그래프의 정점은 프로젝트의 이정표를 나타내며 모서리는 하나의 이정표와 다른 이정표 사이에 수행해야 하는 작업을 나타냅니다.토폴로지 정렬은 프로젝트의 중요한 경로, 일련의 마일스톤 및 전체 프로젝트 스케줄의 길이를 제어하는 태스크를 찾기 위한 선형 시간 알고리즘의 기초를 형성합니다.

컴퓨터 과학에서 이러한 유형의 애플리케이션은 명령 스케줄링, 스프레드시트에서 공식 값을 재계산할 때 공식 셀 평가 순서, 논리 합성, makefile에서 수행할 컴파일 태스크의 순서 결정, 데이터 직렬화 및 링커에서의 기호 종속성 해결에서 발생합니다.또한 데이터베이스의 외부 키로 테이블을 로드하는 순서를 결정하는 데도 사용됩니다.

왼쪽에 표시된 그래프에는 다음과 같은 많은 유효한 토폴로지 정렬이 있습니다.

5, 7, 3, 11, 8, 2, 9, 10 (위에서 아래로, 왼쪽에서 오른쪽으로 시각)
3, 5, 7, 8, 11, 2, 9, 10(사용 가능한 정점부터 162 번호)
5, 7, 3, 8, 11, 10, 9, 2 (가장 낮은 가장자리부터)
7, 5, 11, 3, 10, 8, 9, 2(가장 큰 번호의 사용 가능한 정점 먼저)
5, 7, 11, 2, 3, 8, 9, 10 (위에서 아래로, 왼쪽에서 오른쪽으로 이동)
3, 7, 8, 5, 11, 10, 2, 9 (표준)

알고리즘

통상적인 토폴로지 정렬 알고리즘에서는 노드 수에 O $O(\left|{V}\right|+\left|{E}\right|).$ $).\displaystyle$ O $(\left {V}\right +\left {E}\right)$ 를 더한 실행 시간이 선형으로 표시됩니다. $}$

칸 알고리즘

Kahn(1962)에 의해 처음 기술된 이러한 알고리즘 중 하나는 궁극적인 위상 ^[2]정렬과 같은 순서로 정점을 선택함으로써 작동한다.먼저 들어오는 가장자리가 없는 "시작 노드" 목록을 찾아 세트 S에 삽입합니다. 이러한 노드가 적어도 하나 이상 비어 있지 않은 비순환 그래프에 존재해야 합니다.그 후, 다음과 같이 입력합니다.

L ← 정렬된 요소를 포함할 빈 목록 S ← S가 비어 있지 않은 동안 들어오는 에지가 없는 모든 노드의 집합 S에서 노드 n을 제거하고, n에서 m까지의 에지가 있는 각 노드 m에 대해 노드 n을 L에 추가하며, m에 다른 들어오는 에지가 없는 경우 그래프에서 에지 e를 제거하고, 그래프 에지가 있는 경우 M을 S에 삽입한 다음 반환한다.오류(그래프에 하나 이상의 사이클이 있음) 그렇지 않으면 L(토폴로지적으로 정렬된 순서)이 반환됩니다.

그래프가 DAG인 경우 솔루션이 목록 L에 포함됩니다(솔루션이 반드시 고유할 필요는 없습니다).그렇지 않으면 그래프에 적어도 하나의 주기가 있어야 하므로 위상 정렬이 불가능합니다.

그 결과 발생하는 소트 고유의 것이 아님을 반영하여 구조체 S는 단순한 집합 또는 큐 또는 스택이 될 수 있다.노드 n이 세트 S에서 삭제되는 순서에 따라 다른 솔루션이 작성된다.사전 편찬적으로 관계를 끊는 Kahn 알고리즘의 변형은 병렬 스케줄링과 계층 그래프 그리기를 위한 Coffman-Graham 알고리즘의 핵심 구성요소를 형성합니다.

깊이 우선 검색

위상 정렬을 위한 대체 알고리즘은 깊이 우선 검색에 기초한다.알고리즘은 임의의 순서로 그래프의 각 노드를 루프하여 토폴로지 정렬 시작 이후 이미 방문한 노드에 도달하거나 노드에 발신 에지(리프 노드)가 없을 때 종료되는 깊이 우선 검색을 시작합니다.

L ← 영구 마크가 없는 노드가 존재하는 동안 정렬된 노드를 포함하는 빈 리스트는 n에 영구 마크가 있는 경우 표시되지 않은 노드 n visit(n) 함수 visit(node n)을 선택하고 n에 일시 마크가 있는 경우 n에서 가장자리를 가진 각 노드 m에 대해 임시 마크가 있는 중지(DAG가 아님) 마크 n을 선택하여 방문합니다.(m) L의 선두에 영구 마크 n을 추가하여 n 마크 n에서 임시 마크를 제거한다.

각 노드 n은 n에 의존하는 다른 모든 노드(그래프 중 n의 모든 하위 노드)를 고려한 후에만 출력 리스트 L에 부가된다.구체적으로는 알고리즘에 의해 노드n이 추가되면 n에 의존하는 모든 노드가 이미 출력 리스트L에 있음을 보증합니다.이러한 노드는 n을 방문하기 위한 콜 전에 종료된 재귀적인 visit() 또는 n을 방문하기 위한 콜 전에 시작된 visit()에 의해 L에 추가되었습니다.각 에지 및 노드가 한 번 방문되므로 알고리즘은 선형 시간으로 실행됩니다.이 깊이 우선 검색 기반 알고리즘은 Cormen 등이 기술한 알고리즘이다. ([4]2001);^[3] 1976년 타잔에 의해 인쇄로 처음 기술된 것으로 보인다.

병렬 알고리즘

병렬랜덤액세스머신에서는 다항식수의 프로세서를 사용하여² O(log n)시간 내에 위상순서를 구성할 수 있어 문제를 복잡도 클래스² NC로 ^[5]할 수 있다.이를 위한 한 가지 방법은 최소화 대신 최대화를 사용한 최소화 행렬 곱셈을 사용하여 주어진 그래프의 인접 행렬을 대수적으로 여러 번 반복 제곱하는 것입니다.결과 행렬은 그래프에서 가장 긴 경로 거리를 나타냅니다.가장 긴 착신 경로의 길이에 따라 정점을 정렬하면 위상 ^[6]순서가 생성됩니다.

분산 메모리 기계에서의 병렬 위상 정렬 알고리즘은 $G=(V,E)$ G $G=(V,E)$ ( $G=(V,E)$ , $G=(V,E)$ ) { $style$ G= ( $V, E$ ^[7]에 대한 Kahn의 알고리즘을 병렬화합니다. 높은 수준에서 Kahn의 알고리즘은 indegree 0의 정점을 반복적으로 제거하고 제거된 순서대로 위상 정렬에 추가합니다.제거된 정점의 나가는 모서리도 제거되므로 indegree 0의 새로운 정점 세트가 있으며, 여기서 정점이 남지 않을 때까지 절차가 반복됩니다.이 알고리즘은 D $D+1$ + $(Displaystyle$ D $+1)$ 의 $D+1$ 반복을 $D+1$ 합니다. $여기$ 서 D는 $G$ 에서 가장 긴 경로입니다.각 반복은 병렬화할 수 있습니다.이것은 다음 알고리즘의 개념입니다.

다음 예제에서는 그래프 파티션이 0 $0,\dots ,p-1$ $0,\dots ,p-1$ p $0,\dots ,p-1$ - $0,\dots ,p-1$ (\ $displaystyle$ 0 $,\dots,p-1$ $0,\dots ,p-1$ 이 붙은 p 처리 요소(PE)에 저장되어 있다고 가정합니다.각 $PE$ i는 로컬 $Q_{i}^{1}$ $Q_{i}^{1}$ 1 세트(\ $displaystyle Q_{i}^1})$ 를 $Q_{i}^{1}$ indegree 0으로 초기화합니다.여기서 상위 인덱스는 현재 반복을 나타냅니다.로컬 $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ 0 $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ , $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ , $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ - $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ 1 {\ $displaystyle Q_{0}^{$ 1},\ $dots,Q_{p-1}^1}$ 의 $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ 모든 정점은 indegree 0을 가지므로, 즉 인접하지 않으므로 유효한 토폴로지 정렬을 위해 임의의 순서로 지정할 수 있습니다.각 정점에 글로벌 인덱스를 할당하기 위해 Q $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ 1, $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ - $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ p-1 $Q_{0}^{1},\dots ,Q_{p-1}^{1}$ 1}의 크기에 걸쳐 프리픽스 합계가 계산됩니다. 따라서 각 ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$ 에는 ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$ - ${\textstyle \sum _{i=0}^{p-1}|Q_{i}|}$ Qi (\ $text sum \{i_0_1}^{1})$ 의 값이 있습니다.

2개의 처리 요소를 가진 DAG에서 병렬 토폴로지 정렬 알고리즘을 실행합니다.

첫 번째 단계에서 $PE$ j는 지수 ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ i ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ 0 ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ - ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ 1, ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ( ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ i ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ j ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ 1 ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ ) - $1$ ({i ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ = ${\textstyle \sum _{i=0}^{j-1}|Q_{i}^{1}|,\dots ,\left(\sum _{i=0}^{j}|Q_{i}^{1}|\right)-1}$ 0 }^{ $j-1} Q_{1},\sub,\left(\sum_i=0}^{j-1}^{i$ })^{1},\sum,\left(\sum_{i_{i}^{i}^{i}^1}^{ $i}^1}^$ 1})를 $할당합니다.$ $Q_{j}^{1}$ $Q_{j}^{1}$ 1 $({$ 의 $Q_{j}^{1}$ 이러한 정점은 대응하는 발신 에지와 함께 제거됩니다. $Q_{j}^{1}$ $l,j\neq l$ l $l,j\neq l$ $l,j\neq l$ l \ $displaystyle$ $l$ , $j$ \ $neq$ l $l,j\neq l$ の $(u,v)$ $(u,v)$ edge edge edge edge edge edge ( edge $(u,v)$ （ $(u,v)$ $u$ , v $(u,v)$ ） $(u,v)$ edge ( edge ( ( ( （ u , $v$ ） $edge$ $edge$ edge ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( ( （）에 $Q_{j}^{1}$ 대해 ( $Q_{j}^{1}$ , $(u,v)$ v ) { $displaystyle$ ( $）$ $,$ ) for q q q q l l for for for for l l for for for l l l l l l l l l l l l, l l l l l l l,,,,,수신된 $(u,v)$ 메시지 $,$ v) {{ $displaystyle($ u, v)}은 $(u,v)$ 로컬 $정점$ v의 indegree를 업데이트합니다.indegree가 0으로 떨어지면 $Q_{j}^{2}$ $({$ 에 v가 추가됩니다.그 후 다음 반복이 시작됩니다.

$스텝$ k에서 $PE$ j는 ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 에 ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 1 + ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ i ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ , ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ … , ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ + ( ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ i $= 0 j$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ $i$ k ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ) - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 1 ( { $textstyle$ a $_$ { k - $1$ }^{j - 1 }^{j - 1 } $Q _$ { i }^{ k } 、 \ $textsty$ 、 \ $leftextstyleft$ 、 \ } $k-1$ k - $k-1$ {style $k-1$ $뒤$ 에 삽입된 정점. 이 절차는 처리할 정점이 남아 있지 않을 때까지 반복됩니다.따라서 ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ p - ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ D + $=$ 0 { $textstyle$ \ $sum _$ {i ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ = 0 }^{ $i}^{D+$ 1} $=$ 0 = 0 ${\textstyle \sum _{i=0}^{p-1}|Q_{i}^{D+1}|=0}$ } $Q_{i}$ 아래는 상위 레벨의 유사 코드이며, 다중 프로그램 데이터입니다.

로컬 ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 의 프리픽스 ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 는 k ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ + ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ i ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ j - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ , ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ … , ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ + ( ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ i $=$ $j$ Q $i$ k ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ ) - ${\textstyle a_{k-1}+\sum _{i=0}^{j-1}|Q_{i}^{k}|,\dots ,a_{k-1}+\left(\sum _{i=0}^{j}|Q_{i}^{k}|\right)-1}$ 1 ( { $textstyle$ a $_$ { k - $1$ }^{ j - 1 }^{ $i$ }^{ i }^{ $k$ }^{ k } , \ $textsum$ 、 \ 、 \ 、 \ { i }^{ $i$ }^{ k - 1 $left$ left ）、 \ 、 \ (((((((( note $note$ note((((( note

ID가 0 ~ p-1인 p 처리 요소 입력: G = (V, E) DAG, PE에 분산됨, PE 인덱스 j = 0, ..., p - 1 출력: G 함수 transparsDAGDistributed vertices 로컬 정점의 수신 정도  $V$  Q = { $v$  ∈ v =  $0/ l$ ]Q//의 크기에 대한 Refix 합 QlocalOrder[u]에+sum(치, 나는 조향 개시 0으로 j-1)을 끓여j는 프로세서 지수 foreach uxindex++, E에서 foreach(u,v)체육에 대한 직시를 1메시지(u, v) 하는 오프셋과 vertices의 이 단계에서 총 오프셋 값)nrOfVerticesProcessed다.iNg꼭지점 vnrOfVerticesProcessed += sum(치, 나는 초기 조향 순간 0p-1)vertices의 Q에 이웃들에게 VQforeach 메시지(u, v)의 모든 vertices 받은을 제거해 지역 vertices에 메시지를 받:만약--δ[v]=0Q의 세계적인 크기 을 Q;v를 추가하 0반환 인용 모든 메시지를 전달하다.alOr데루

통신 비용은 주어진 그래프 파티션에 크게 의존합니다.런타임에 대해서는 일정한 시간에 fetch-and-decrement를 허용하는 CRCW-PRAM 모델에서 이 알고리즘은 ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ O ( ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ + ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ + ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ D ) ( ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ + ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ n ${\textstyle {\mathcal {O}}\left({\frac {m+n}{p}}+D(\Delta +\log n)\right)}$ \ $textstyle$ { $O$ } \ left ( { \ $frac { m$ + n } { $p$ + $Del$ + $log$ \ $log$ \ light $)$ 로 실행됩니다 $.$

최단 경로 검색 응용 프로그램 적용

토폴로지 순서를 사용하여 가중치 유도 비순환 그래프를 통해 최단 경로를 신속하게 계산할 수도 있습니다.V를 이러한 그래프에서 위상 순서로 꼭지점 리스트라고 $합니다$ .그런 다음 다음 다음 알고리즘은 $일부$ 소스 정점에서 다른 모든 ^[3]정점으로 가는 최단 경로를 계산합니다.

d를 V와 $같은$ 길이의 배열로 $합니다$ .이 배열은 에서 최단 경로 거리를 유지합니다.d $[s]$ = $0$ , 기타 $모든$ d $[u]$ = $\infty$ 로 $설정$ 합니다.
p를 V와 $같은$ 길이의 배열로 $하고$ 모든 요소를 다음과 같이 초기화합니다.0. 각 p $[u]$ 는 $s$ 에서 $u$ 까지의 최단 경로로 $u$ 의 선행자를 유지합니다.
s:부터 시작하여 V의 $순서$ 에 따라 $정점$ u를 루프합니다.
- u 바로 $뒤$ 의 각 $정점$ v에 대해(즉, u에서 $v$ 까지 가장자리가 있음):
  - $u$ 에서 v까지의 $가장자리$ 무게로 $합니다$ .
  - 엣지를 완화합니다. $d$ [ v ]> $d$ [ $u]+$ $w$ 의 $경우$ 는,
    - $d [v]$ ← $d [u]$ + $w$ ,
    - $p [v]$ ← $u$ .

동등:

d를 V와 $같은$ 길이의 배열로 $합니다$ .이 배열은 에서 최단 경로 거리를 유지합니다.d $[s]$ = $0$ , 기타 $모든$ d $[u]$ = $\infty$ 로 $설정$ 합니다.
p를 V와 $같은$ 길이의 배열로 $하고$ 모든 요소를 0으로 초기화합니다.각 p $[u]$ 는 $s에서u$ 까지의 최단 경로로 $u$ 의 이전 p[u]를 유지합니다.
s:부터 시작하여 V의 $순서$ 에 따라 $정점$ u를 루프합니다.
- $u$ 로 들어가는 각 정점에 $대해$ (즉, $v$ 에서 u까지의 가장자리가 있음):
  - $v$ 에서 u까지의 $가장자리$ 무게로 합니다.
  - 가장자리를 완화합니다. $d [u]$ > $d [v$ ] + $w$ 의 $경우$ ,
    - $d [u]$ ← $d [v]$ + $w$ ,
    - $p [u]$ ← $v$ .

n개의 $정점$ 과 m개의 에지로 $구성$ 된 그래프에서 이 알고리즘은 ^[3] $δ ($ n + $m$ ), 즉 선형 시간이 걸립니다.

고유성

위상 정렬에 정렬된 순서대로 연속된 모든 정점 쌍이 에지로 연결되는 특성이 있는 경우, 이러한 에지는 DAG에서 방향성 해밀턴 경로를 형성합니다.해밀턴 경로가 존재하는 경우 토폴로지 정렬 순서는 고유하며 경로의 가장자리에 해당하는 다른 순서는 없습니다.반대로 토폴로지 정렬이 해밀턴 경로를 형성하지 않으면 DAG는 두 개 이상의 유효한 토폴로지 순서를 갖게 됩니다.이 경우 항상 에지로 연결되지 않은 두 개의 연속된 정점을 서로 교환하여 두 번째 유효한 순서를 형성할 수 있기 때문입니다.따라서, 보다 일반적인 방향 그래프(즉, 순환 방향 그래프)^[8]에 대한 해밀턴 경로 문제의 NP-경도에도 불구하고, 고유한 순서가 존재하는지 여부와 해밀턴 경로의 존재 여부를 선형 시간에 테스트할 수 있다.

부분주문과의 관계

위상 순서는 수학에서 부분 순서의 선형 확장 개념과도 밀접하게 관련되어 있습니다.부분 순서 집합은 반사율(x x x), 반대칭성(x y y와 y x y의 경우 x = y의 경우) 및 전달성(x z y와 y z z의 경우 x oms z의 경우)의 공리를 만족시키는 "부등식" 부등 관계의 정의와 함께 단지 물체 집합이다.전체 순서는 집합 내 2개의 객체 x 및 y마다 x y y 또는 y x x 중 하나의 부분 순서입니다.전체 순서는 비교 정렬 알고리즘을 실행하는 데 필요한 비교 연산자로서 컴퓨터 과학에서 잘 알려져 있습니다.유한 집합의 경우, 총 순서는 객체의 선형 시퀀스로 식별될 수 있으며, 여기서 "θ" 관계는 첫 번째 객체가 순서에서 두 번째 객체 앞에 있을 때마다 참이다. 비교 정렬 알고리즘을 사용하여 총 순서를 시퀀스로 변환할 수 있다.부분순서의 선형연장은 부분순서의 x in y일 경우 전체순서의 x y y라는 의미에서의 그것과 호환되는 전체순서입니다.

임의의 DAG로부터의 부분 순서를 정의할 수 있습니다.객체 세트를 DAG의 정점으로 하고 x에서 y로의 유도 경로가 존재할 때마다 x와 y의 임의의 2개의 정점에 대해 x µ y를 참으로 정의합니다.이러한 정의에서 DAG의 토폴로지 순서는 이 부분 순서의 선형 확장과 동일합니다.반대로, DAG의 도달 가능성 관계로서 임의의 부분 순서를 정의할 수 있습니다.이를 위한 한 가지 방법은 부분적으로 순서가 매겨진 집합의 모든 객체에 대해 정점을 갖는 DAG와 x µ y인 모든 객체 쌍에 대해 가장자리 xy를 정의하는 것입니다.다른 방법으로는 부분순서의 트랜시셔널 리덕션을 사용하는 방법이 있습니다.일반적으로 이렇게 하면 에지가 적은 DAG가 생성되지만 이들 DAG의 도달 가능성 관계는 여전히 동일한 부분순서입니다.이러한 구조를 사용하면 위상 순서 알고리즘을 사용하여 부분 순서의 선형 확장을 찾을 수 있습니다.

스케줄링 최적화와의 관계

정의에 따르면 우선순위 그래프를 포함하는 스케줄링 문제의 솔루션은 (머신의 수에 관계없이) 토폴로지 정렬에 대한 유효한 솔루션이지만, 토폴로지 정렬 자체는 스케줄링 최적화 문제를 최적으로 해결하기에 충분하지 않습니다.Hu의 알고리즘은 우선순위 그래프가 필요하고 처리 시간이 수반되는 스케줄링 문제를 해결하기 위해 널리 사용되는 방법입니다(모든 작업 중 가장 큰 완료 시간을 최소화하는 것이 목표입니다).위상 정렬과 마찬가지로 Hu의 알고리즘은 고유하지 않으며 DFS를 사용하여 해결할 수 있습니다(최대 경로 길이를 찾은 다음 작업을 할당).

「」를 참조해 주세요.

tsort, 토폴로지 정렬용 Unix 프로그램
피드백 호 세트, 제거하여 나머지 하위 그래프를 위상적으로 정렬할 수 있는 모서리 세트
Tarjan의 견고하게 연결된 컴포넌트 알고리즘, 강력하게 연결된 컴포넌트의 토폴로지적으로 정렬된 목록을 그래프에 표시하는 알고리즘
토폴로지 전 순서

레퍼런스

^ Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory
^ Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562, doi:10.1145/368996.369025, S2CID 16728233
^ ^a ^b ^c Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.4: Topological sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 549–552, ISBN 0-262-03293-7
^ Tarjan, Robert E. (1976), "Edge-disjoint spanning trees and depth-first search", Acta Informatica, 6 (2): 171–185, doi:10.1007/BF00268499, S2CID 12044793
^ Cook, Stephen A. (1985), "A Taxonomy of Problems with Fast Parallel Algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3
^ Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Parallel matrix and graph algorithms", SIAM Journal on Computing, 10 (4): 657–675, doi:10.1137/0210049, MR 0635424
^ ^a ^b Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019), Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Springer International Publishing, ISBN 978-3-030-25208-3
^ Vernet, Oswaldo; Markenzon, Lilian (1997), "Hamiltonian problems for reducible flowgraphs" (PDF), Proceedings: 17th International Conference of the Chilean Computer Science Society, pp. 264–267, doi:10.1109/SCCC.1997.637099, hdl:11422/2585, S2CID 206554481

추가 정보

D. E. Knuth, The Art of Computer Programming, Volume 1, 섹션 2.2.3, 부분 순서의 위상 정렬 알고리즘과 간단한 이력을 제공합니다.

외부 링크

[Jarnagin-1] Jarnagin, M. P. (1960), Automatic machine methods of testing PERT networks for consistency, Technical Memorandum No. K-24/60, Dahlgren, Virginia: U. S. Naval Weapons Laboratory

[Kahn-2] Kahn, Arthur B. (1962), "Topological sorting of large networks", Communications of the ACM, 5 (11): 558–562, doi:10.1145/368996.369025, S2CID 16728233

[CLRS-3] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "Section 22.4: Topological sort", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 549–552, ISBN 0-262-03293-7

[Tarjan-4] Tarjan, Robert E. (1976), "Edge-disjoint spanning trees and depth-first search", Acta Informatica, 6 (2): 171–185, doi:10.1007/BF00268499, S2CID 12044793

[Cook-5] Cook, Stephen A. (1985), "A Taxonomy of Problems with Fast Parallel Algorithms", Information and Control, 64 (1–3): 2–22, doi:10.1016/S0019-9958(85)80041-3

[DNS-6] Dekel, Eliezer; Nassimi, David; Sahni, Sartaj (1981), "Parallel matrix and graph algorithms", SIAM Journal on Computing, 10 (4): 657–675, doi:10.1137/0210049, MR 0635424

[SMDD-7] Sanders, Peter; Mehlhorn, Kurt; Dietzfelbinger, Martin; Dementiev, Roman (2019), Sequential and Parallel Algorithms and Data Structures: The Basic Toolbox, Springer International Publishing, ISBN 978-3-030-25208-3

[VM-8] Vernet, Oswaldo; Markenzon, Lilian (1997), "Hamiltonian problems for reducible flowgraphs" (PDF), Proceedings: 17th International Conference of the Chilean Computer Science Society, pp. 264–267, doi:10.1109/SCCC.1997.637099, hdl:11422/2585, S2CID 206554481

[1]

[2]

[3]

[5]

[6]

[7]

[8]

v t 정렬 알고리즘
이론.	계산 복잡도 이론 빅 O 표기법 총주문량 리스트 배치 안정성. 비교 정렬 적응 정렬 네트워크 정렬 정수 정렬 X + Y 정렬 트랜스디코모형 양자 정렬
교환 정렬	버블 정렬 칵테일 셰이커 종류 홀수-짝수 정렬 빗살 정렬 노메 소트 비율 연장 정렬 퀵소트 슬로우소트 스투지 종류 보고소트
선택 정렬	선택 정렬 힙소트 스무스소트 데카르트 트리 정렬 토너먼트 소트 사이클 정렬 약한 굽의 종류
삽입 정렬	삽입 정렬 셸소트 스플래시소트 트리 정렬 라이브러리 정렬 인내심 분류
병합 정렬	병합 정렬 캐스케이드 머지 정렬 진동 병합 정렬 다상 병합 정렬
배포 정렬	성조기 분류 구슬 정렬 버킷 정렬 버스트소트 카운트 정렬 보간 정렬 비둘기구멍 분류 프록시 맵 정렬 기수 정렬 플래시 소트
동시 정렬	역청 선별기 배처 홀수 짝수 머지소트 쌍방향 정렬 네트워크 샘플 정렬
잡종 종류	블록 병합 정렬 커크패트릭-라이시 종류 팀소트 인트로소트 스프레드소트 병합-삽입 정렬
다른.	토폴로지 정렬 토폴로지 전 순서 팬케이크 구분 스파게티 정렬

v t 데이터 구조 및 알고리즘
데이터 구조	어레이 연관 배열 이진 검색 트리 펜윅나무 그래프 해시 테이블 히프 링크 리스트 큐 세그먼트 트리 스택 스트링 트리 트리
알고리즘	역추적 바이너리 검색 폭 우선 검색 깊이 우선 검색 분열시켜 정복하다. 동적 프로그래밍 접다 욕심쟁이 미니맥스 재귀 정렬 스트리밍 스위프 라인 토폴로지 정렬
데이터 구조 목록 알고리즘 목록

Search

토폴로지 정렬

네임스페이스

더

목차

예

알고리즘

칸 알고리즘

깊이 우선 검색

병렬 알고리즘

최단 경로 검색 응용 프로그램 적용

고유성

부분주문과의 관계

스케줄링 최적화와의 관계

「」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

Search

토폴로지 정렬

예

알고리즘

칸 알고리즘

깊이 우선 검색

병렬 알고리즘

최단 경로 검색 응용 프로그램 적용

고유성

부분주문과의 관계

스케줄링 최적화와의 관계

「 」를 참조해 주세요.

레퍼런스

추가 정보

외부 링크

「」를 참조해 주세요.