Топологический порядок ориентированного ациклического графика
n = toposort(G)G таким образом i < j для каждого ребра (n(i),n(j)) в G. Ориентированный график G не может иметь никаких циклов.
Создайте и постройте график, который представляет прогрессию курсов математики университетского уровня. Ребро между двумя курсами означает требование к курсу.
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' }
Создайте ориентированный граф с помощью логической матрицы смежности, а затем постройте график.
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
digraph | isdag | reordernodes