Топологический порядок направленного ациклического графа
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