이 번역 페이지는 최신 내용을 담고 있지 않습니다. 최신 내용을 영문으로 보려면 여기를 클릭하십시오.

toposort

R2026a

유방향 비순환 그래프의 위상 순서(Topological Order)

구문

n = toposort(G)

n = toposort(G,'Order',algorithm)

[n,H] = toposort(___)

설명

n = toposort(G)는 G에 있는 노드의 위상 순서를 반환합니다(예: G에 있는 모든 간선 (n(i),n(j))의 경우 i < j). 유방향 그래프 G는 순환을 가질 수 없습니다.

n = toposort(G,'Order',algorithm)은 정렬 알고리즘(Ordering Algorithm)을 지정합니다. 예를 들어, toposort(G,'Order','stable')은 노드의 사전식 순서를 따르는 안정적(Stable) 정렬 알고리즘을 사용합니다.

[n,H] = toposort(___)는 노드가 지정된 위상 순서로 정렬된 유방향 그래프 H를 추가적으로 반환합니다. 위에 열거된 구문에 나와 있는 입력 인수를 원하는 대로 조합하여 사용할 수 있습니다.

예제

노드의 위상 정렬

대학교 수학 강의들 간의 수강 구조를 나타내는 그래프를 생성하고 플로팅합니다. 두 수학 강의 사이의 간선은 수강 필요성을 의미합니다.

A = [0 1 1 0 0 0 0
     0 0 0 1 0 0 0
     0 1 0 1 0 0 1
     0 0 0 0 1 1 0
     0 0 0 0 0 0 0
     0 0 0 0 1 0 0
     0 0 0 0 1 0 0];
names = {'Calculus I','Linear Algebra','Calculus II', ...
    'Multivariate Calculus','Topology', ...
    'Differential Equations','Real Analysis'};
G = digraph(A,names);
plot(G)

수학 강의들 간의 위상 정렬을 찾아 어떤 순서로 수강을 해야 하는지 적절한 순서를 확인합니다.

N = toposort(G)

N = 1×7

     1     3     7     2     4     6     5

G.Nodes.Name(N,:)

ans = 7×1 cell
    {'Calculus I'            }
    {'Calculus II'           }
    {'Real Analysis'         }
    {'Linear Algebra'        }
    {'Multivariate Calculus' }
    {'Differential Equations'}
    {'Topology'              }

안정적인 위상 정렬(Stable Topological Sort)

논리형 인접 행렬을 사용하여 유방향 그래프를 생성한 다음 이 그래프를 플로팅합니다.

rng default;
A = tril(sprand(10, 10, 0.3), -1)~=0;
G = digraph(A);
[~,G] = toposort(G);
plot(G)

그래프 노드의 위상 정렬을 찾습니다. G가 이미 위상 순서 (1 2 3 4 5 6 7 8 9 10)으로 정렬되어 있더라도, toposort는 노드를 재정렬합니다.

toposort(G)

ans = 1×10

     2     1     4    10     9     8     5     7     3     6

안정적인 정렬 알고리즘을 사용하려면 Order를 'stable'로 지정하십시오. 그러면 인덱스가 더 작은 노드가 우선이 되는 순서로 정렬됩니다. 안정적인 정렬은 G가 이미 위상 순서로 정렬되어 있으면 재배열하지 않습니다.

toposort(G,'Order','stable')

ans = 1×10

     1     2     3     4     5     6     7     8     9    10

입력 인수

G — 입력 그래프

digraph 객체

입력 그래프로, digraph 객체로 지정됩니다. G는 유방향 비순환 그래프여야 합니다. isdag를 사용하여 G에 순환이 없음을 확인할 수 있습니다.

digraph를 사용하여 유방향 그래프를 생성할 수 있습니다.

예: G = digraph([1 2],[2 3])

algorithm — 정렬 알고리즘

'fast' (디폴트 값) | 'stable'

정렬 알고리즘(Ordering Algorithm)으로, 다음과 같은 'fast' 또는 'stable'로 지정됩니다.

'fast'(디폴트 값)	깊이 우선 탐색(Depth-first Search)을 기반으로 합니다. 한 노드의 후속 노드(후손)를 모두 고려한 다음 이 노드를 그 목록의 시작 부분에 추가합니다. G가 이미 위상 순서로 정렬되어 있어도 이 방법은 여전히 노드를 재정렬할 수 있습니다.
'stable'	사전식 순서(Lexicographical Order)를 기반으로 합니다. n(1)은 인덱스가 가장 작은 노드가 되고, n(2)는 지정된 n(1) 다음으로 가장 작은 인덱스가 되는 식으로 정렬됩니다. G가 이미 위상 순서로 정렬되어 있으면 H는 변경되지 않으며, n은 1:numnodes(G)가 됩니다.

예: [n,H] = toposort(G,'Order','stable')

출력 인수

n — 노드 인덱스

행 벡터

노드 인덱스로, 행 벡터로 반환됩니다.

H — 위상 정렬된 그래프

digraph 객체

위상 정렬된 그래프(Topologically Sorted Graph)로, digraph 객체로 반환됩니다. H는 G와 동일한 그래프이지만, n에 따라 노드가 재정렬됩니다.

세부 정보

위상 순서

유방향 그래프의 위상 정렬은 그래프에 있는 노드의 정렬로, 각 노드가 자신의 후속 노드(후손) 앞에 표시됩니다.

노드가 작업을 나타내고 해당 간선이 특정 작업을 다른 작업 이전에 완료해야 하는 종속성을 나타내는 유방향 그래프가 있다고 가정해 보십시오. 이러한 그래프의 경우 그래프 노드를 위상 정렬하면 의미 있는 작업 수행 순서를 파악해 낼 수 있습니다.

버전 내역

R2015b에 개발됨

참고 항목

digraph | isdag | reordernodes