toposort
유방향 비순환 그래프의 위상 순서(Topological Order)
설명
예제
노드의 위상 정렬
대학교 수학 강의들 간의 수강 구조를 나타내는 그래프를 생성하고 플로팅합니다. 두 수학 강의 사이의 간선은 수강 필요성을 의미합니다.
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 = 7x1 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
입력 인수
algorithm
— 정렬 알고리즘
'fast'
(디폴트 값) | 'stable'
정렬 알고리즘(Ordering Algorithm)으로, 다음과 같은 'fast'
또는 'stable'
로 지정됩니다.
'fast' (디폴트 값) | 깊이 우선 탐색(Depth-first Search)을 기반으로 합니다. 한 노드의 후속 노드(후손)를 모두 고려한 다음 이 노드를 그 목록의 시작 부분에 추가합니다.
|
'stable' | 사전식 순서(Lexicographical Order)를 기반으로 합니다.
|
예: [n,H] = toposort(G,'Order','stable')
출력 인수
n
— 노드 인덱스
행 벡터
노드 인덱스로, 행 벡터로 반환됩니다.
H
— 위상 정렬된 그래프
digraph
객체
위상 정렬된 그래프(Topologically Sorted Graph)로, digraph
객체로 반환됩니다. H
는 G
와 동일한 그래프이지만, n
에 따라 노드가 재정렬됩니다.
세부 정보
위상 순서
유방향 그래프의 위상 정렬은 그래프에 있는 노드의 정렬로, 각 노드가 자신의 후속 노드(후손) 앞에 표시됩니다.
노드가 작업을 나타내고 해당 간선이 특정 작업을 다른 작업 이전에 완료해야 하는 종속성을 나타내는 유방향 그래프가 있다고 가정해 보십시오. 이러한 그래프의 경우 그래프 노드를 위상 정렬하면 의미 있는 작업 수행 순서를 파악해 낼 수 있습니다.
버전 내역
R2015b에 개발됨
참고 항목
digraph
| isdag
| reordernodes
MATLAB 명령
다음 MATLAB 명령에 해당하는 링크를 클릭했습니다.
명령을 실행하려면 MATLAB 명령 창에 입력하십시오. 웹 브라우저는 MATLAB 명령을 지원하지 않습니다.
Select a Web Site
Choose a web site to get translated content where available and see local events and offers. Based on your location, we recommend that you select: .
You can also select a web site from the following list:
How to Get Best Site Performance
Select the China site (in Chinese or English) for best site performance. Other MathWorks country sites are not optimized for visits from your location.
Americas
- América Latina (Español)
- Canada (English)
- United States (English)
Europe
- Belgium (English)
- Denmark (English)
- Deutschland (Deutsch)
- España (Español)
- Finland (English)
- France (Français)
- Ireland (English)
- Italia (Italiano)
- Luxembourg (English)
- Netherlands (English)
- Norway (English)
- Österreich (Deutsch)
- Portugal (English)
- Sweden (English)
- Switzerland
- United Kingdom (English)